+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- "بیا" تصمیم گرفته است که از شکرستان به نمکستان سفر کند. او می‌داند که در این حوالی $n$ شهر با شماره‌های ۱ تا $n$ (شکرستان شهر شماره ۱ و نمکستان شهر شماره $n$) و $m$ جاده دو طرفه بین این شهرها وجود دارد. می‌دانیم بین هر دو شهر حداکثر یک جاده قرار دارد و برای هر جاده می‌دانیم طی کردن آن چقدر طول می‌کشد. او نمی‌خواهد در سفر خود از یک شهر دو بار عبور کند.  به تازگی دانشمندان شکرستان سیستم ارتباطی عجیبی به نام "بدو بیا" در بعضی از این $n$ شهر راه انداختند. این سیستم به این صورت کار می‌کند که اگر یک شهر دارای این سیستم باشد می‌تواند پس از $t$ ثانیه از یک شهر به یک شهر دیگر که دارای این سیستم است برود. قسمت عجیب این سیستم اینجاست که ممکن است، این عدد $t$ منفی باشد! در صورتی که می تواند چنین سفری را انجام دهد، حداقل زمانی که طول می‌کشد تا از شکرستان به نمکستان سفر کند چقدر است؟ (عجیب است که این مقدار نیز می‌تواند منفی باشد!) # ورودی در سطر اول ورودی سه عدد $n$ و $m$ و $t$ آمده است که به ترتیب نمایانگر تعداد شهرها ، جاده‌ها و مقدار $t$ هستند. شکرستان شهر شماره 1 و نمکستان شهر شماره $n$ است. در سطر دوم یک رشته با $n$ حرف آمده‌است که $i$امین حرف آن برابر ۱ است اگر و تنها اگر در راس شماره $i$ سیستم ارتباطی "بدو بیا" وجود داشته باشد و در غیر این صورت $i$امین حرف رشته برابر ۰ است. سپس در $i$امین سطر از هریک از $m$ سطر بعدی سه عدد $u_i$ و $v_i$ و $w_i$ آمده‌اند که دو شهر انتهایی و زمان طی کردن جاده بین این دو شهر را نشان می‌دهد. در ورودی‌های این سوال تضمین می‌شود که بین هر دو شهر حداکثر یک جاده از این $m$ جاده موجود است و دو شهر انتهایی یک جاده یکسان نیستند. $$ 2 \le n \le 1\ 000 $$ $$1 \le m \le 1\ 000$$ $$ 1 \le u_i, v_i \le n $$ $$|t| \le 1\ 000\ 000$$ $$ 1 \le w_i \le 1\ 000\ 000 $$ # خروجی در تنها سطر خروجی یک عدد چاپ کنید که برابر کمترین زمانی است که طول می‌کشد تا از شکرستان به نمکستان سفر کند. در صورتی که نمی‌تواند چنین سفری را انجام دهد، کلمه‌ی $"Impossible"$ را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 2 3 101 1 2 2 2 3 2 ``` ## خروجی نمونه ۱ ``` 3 ``` ## ورودی نمونه ۲ ``` 4 4 -6 0110 1 2 2 2 3 2 3 4 2 1 4 1 ``` ## خروجی نمونه ۲ ``` -2 ``` ## ورودی نمونه ۳ ``` 4 2 10 1000 1 2 1 2 3 1 ``` ## خروجی نمونه ۳ ``` Impossible ```

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