+ محدودیت زمان: ۶ ثانیه + محدودیت حافظه: ۱۰۲۴ مگابایت ---------- پس از شنیدن خبر اعزام به قزاقستان، شاختک سریعا چمدان خود را جمع کرد تا به سمت شهر آستانه راهی شود. دریغ از آنکه در این عملیات فوق سری و گروهی او با پیرهرات و دامغانیاندی، برای سفر هوایی نیاز به پاسپورت داشتند و دامغانیاندی تا به حال چیزی از پاسپورت نشنیده بود. به همین جهت، تصمیم بر آن شد به صورت زمینی خود را به یکی از شهر‌های مرزی قزاقستان به نام آلماتی برسانند و از آن‌جا تا آستانه را پیاده بروند. حال که هر سه به آلماتی (شهر با شماره‌ی ۱) رسیده‌اند، نقشه‌ی قزاقستان را تهیه کرده و می‌خواهند به سمت آستانه (شهر با شماره‌ی $n$) حرکت کنند. نقشه‌ی قزاقزستان از $n$ شهر و $m$ جاده‌ی **یک‌طرفه** بین شهر‌ها تشکیل شده‌است. هر جاده بین دو شهر قرار دارد و **ممکن است** از یک شهر به خودش جاده‌ای باشد و یا از شهر $u$ به شهر $v$ بیش از یک جاده موجود باشد. به دلایلی نامعلوم، هر جاده با تعدادی از $k$ رنگ موجود رنگ شده است. به دلیل پیچیده بودن نقشه، هر سه نفر توافق کردند تا به شکل زیر حرکت کنند: + زمانی که در شهری مانند $v$ قرار دارند، ابتدا شاختک یکی از $k$ رنگ استفاده شده در نقشه را انتخاب کند. سپس پیرهرات و دامغانیاندی یکی از جاده‌هایی که از $v$ شروع می‌شوند و رنگ انتخاب شده‌ی شاختک در آن‌ها به کار رفته است را برگزینند و هر سه از آن جاده بگذرند. پیرهرات و دامغانیاندی که از سفر زمینی بسیار خسته شده‌اند، قصد دارند در دیرترین زمان ممکن به آستانه برسند (یا کاری کنند که هیچ‌گاه نتوان به آستانه رسید)، اما شاختک که بسیار مشتاق است، دوست دارد در نزدیک‌ترین زمان ممکن به آستانه برود. در صورتی که هر دو گروه بازی بهینه‌ای انجام دهند، تعیین کنید چه زمانی به آستانه می‌رسند. (یا بگویید هیچ‌گاه به آستانه نمی‌رسند.) # ورودی در خط اول ورودی، سه عدد $n$ تعداد شهر‌ها، $m$ تعداد جاده‌ها و $k$ تعداد رنگ‌های به کار رفته در نقشه داده می‌شوند. در $2m$ خط بعدی، در هر دو خط توضیح یکی از جاده‌ها داده شده است. + در خط اول توضیح هر جاده، سه عدد $u$، $v$ و $t$ آمده که به ترتیب، شهر ابتدای جاده، شهر انتهای جاده، و مدت زمانی که طول می‌کشد از جاده عبور کنند می‌باشد. + در خط دوم، ابتدا یک عدد $l$ نمایانگر تعداد رنگ‌های به کار رفته در جاده‌ی داده شده و سپس، $l$ عدد $a_1, a_2, ..., a_l$ داده می‌شوند که شماره‌ی رنگ‌های به کار رفته در کشیدن جاده می‌باشند. $$1 \le n, m \le 5 \times 10^5$$ $$1 \le k \le 1000$$ $$1 \le u, v \le n$$ $$1 \le t \le 10^6$$ $$1 \le l \le k$$ $$1 \le a_i \le k, i \in \{1, 2, ..., l\}$$ مجموع $l$ها برای تمام جاده‌ها کوچک‌تر یا مساوی $5 \times 10^5$ می‌باشد. دقت کنید که جاده‌ها **یک‌طرفه** هستند. دقت کنید ممکن است چند جاده از شهر $u$ به شهر $v$ وجود داشته باشد. همچنین ممکن است از شهری به خودش جاده وجود داشته باشد. ممکن است دو شهر $x$ و $y$ ای وجود داشته باشند که نتوان از $x$ به $y$ با استفاده از جاده‌ها رسید. # خروجی در تنها سطر خروجی، زمانی که طول می‌کشد گروه از آلماتی (شهر با شماره‌ی ۱) به آستانه (شهر با شماره‌ی $n$) برسد را چاپ کنید. در صورتی که هیچ‌گاه نمی‌توان از آلماتی به آستانه رسید، عبارت `impossible` را چاپ کنید. ## ورودی نمونه ۱ ``` 4 6 2 1 2 6 1 1 1 3 3 1 2 2 3 5 1 2 2 4 8 1 1 3 1 4 2 1 2 3 4 3 1 1 ``` ## خروجی نمونه ۱ ``` 14 ``` فراموش نکنید که جاده‌ها **یک‌طرفه** هستند. ## ورودی نمونه ۲ ``` 3 4 3 1 2 300 2 1 2 2 1 2000 2 3 1 1 3 80 2 2 1 2 2 42 1 2 ``` ## خروجی نمونه ۲ ``` impossible ```

حل سؤال در بانک سؤالات