‎«جناب امپراطور‎!‎ خبری برای شما دارم. در شهر مرزی اوکچه بانو ایسویا را دیدم، متأسفانه ایشون سریع داخل جمعیت ناپدید شدند ولی مطمئن هستم خودشان بودند». این پیغامی بود که اویی - فرستاده‌ی امپراطور - بعد از بازگشت از اوکچه شمالی، به جومونگ - امپراطورِ گوگوریو، داد. حالا جومونگ می‌خواهد به اوکچه شمالی برود تا بانو ایسویا را پیدا کند.

نقشه امپراطوری گوگوریو بصورت یک گراف‌وزن دار بدون‌جهت داده شده است. رئوس این گراف شهرهای امپراطوری گوگوریو هستند و هر یال یک جاده بین آن‌ها. شهرها از ‎۱‎ تا ‎$N$‎ شماره‌گذاری شده‌اند و وزن هر یال مدت زمانی است که طی کردن جاده‌ی متناظر آن طول می‌کشد. شماره‌ی شهر گوگوریو - مرکز امپراطوری گوگوریو، همان شهری که جومونگ در آن قرار دارد- ‎۱‎ و شماره شهر اوکچه شمالی که بانو ایسایو در آن قرار دارد ‎$N$‎ است.

جومونگ باید مسافت بین دو شهر را با اسب بپیماید. در حال حاضر در بعضی شهرها اسب قرار دارد که جومونگ و هم‌چنین ما از آن‌ها باخبر هستیم و در ورودی آن‌ها را به شما می‌دهیم. با هر اسب می‌توان از شهری که اسب در آن قرار داشته تا یک یا دو شهر دورتر رفت. ولی از آن دورتر نمی‌توان رفت، یعنی می‌توان از رأس ‎$x$‎ که اسب در آن قرار دارد به رأس ‎$y$‎ و سپس اگر خواستیم به رأس ‎$z$‎ برویم اگر بین ‎$x$‎ و ‎$y$‎ یال وجود داشته باشد و همچنین بین ‎$y$‎ و ‎$z$‎ یال وجود داشته باشد، مستقل از اینکه وزن آن دو یال چه باشد. از آنجا که جومونگ در اسرع وقت راه می‌افتد، او نمی‌خواهد دستور بدهد تا اسب‌ها را برایش جابه‌جا کنند. بنابراین برای استفاده کردن از هر اسب باید به آن اسب برسد و قبل از رسیدن به شهری که اسب در آن قرار دارد اسب از آنجا تکان نمی‌خورد.

شما باید مسیری را برای رسیدن جومونگ به شهر اوکچه شمالی با استفاده از اسب‌های داده شده بیابید که زمان پیمودن آن کمینه باشد.

• در سطر اول ورودی، سه عدد ‎$N$ (تعداد رئوس نقشه)، ‎$E$ (تعداد یال‌های نقشه) و ‎$K$ (تعداد اسب‌ها) به ترتیب داده شده است.
• در سطر دوم ‎$K$‎ عدد آمده است که شماره رئوسی هستند که اسب‌ها در آن‌ها قرار دارند.
• در ‎$E$‎ سطر بعد، در هر سطر سه عدد ‎$u_i$‎، ‎$v_i$‎ و ‎$w_i$‎ آمده‌اند. ‎$u_i$‎ و ‎$v_i$‎ دوسر یال دوطرفه ‎$i$‎ام هستند و ‎$w_i$‎ وزن آن یال است.
• ‎$1 \le K \le N \le 2000$‎.‎
• ‎$0 \le E \le 100000$‎.
• ‎$0 \le W_i \le 10000$‎.

اگر مسیری از رأس ‎۱‎ به رأس ‎$N$‎ام با استفاده از اسب‌های مذکور وجود داشت در تنها سطر خروجی مجموع وزن یال‌های کم‌وزن‌ترین مسیر را بنویسید. در غیر این صورت فقط بنویسید ‎impossible‎.

برنامه شما برای گرفتن نمرهٔ تست‌هایی که جواب آن‌ها ‎impossible‎ است می‌بایست حداقل به یکی از تست‌هایی که جواب آن‌ها ‎impossible‎ نیست پاسخ درست بدهد.

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل

‎‎