+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در کشور(!) شلمرود، $n$ شهر وجود دارد که با $m$ جاده دوطرفه به هم وصل شده‌اند.‌ طول جاده $i$ام هم $w_i$ کیلومتر است. حسنی یک الاغ هم دارد که با استفاده از آن می‌تواند با سرعت یک کیلومتر بر ساعت جاده‌ها را طی کند. حسنی جدیدا یک قابلیت جدید پیدا کرده که با استفاده از آن می‌تواند طول همه جاده‌ها را یک کیلومتر کم کند. حسنی فقط می‌تواند این قابلیت را وقتی درون یک شهر هست استفاده کند و $t_i$ ساعت طول می‌کشد که از این قابلیت در راس $i$-ام استفاده کند. هم‌چنین اگر با استفاده از این قابلیت طول یک جاده صفر بشود آن جاده از شلمرود حذف می‌شود و نمی‌توان از آن عبور کرد. حالا حسنی از شما می‌پرسد که کم‌ترین زمانی که طول می‌کشد تا از شهر شماره $1$ به شهر شماره $n$ برسه چه قدر هست و از آن‌جا که شما هم حسنی را خیلی دوست دارید باید جوابش را بدهید. # ورودی در خط اول ورودی $n$ و $m$ آمده‌ است. سپس در خط بعدی $n$ عدد آمده که عدد $i$-ام $t_i$ را نشان می‌دهد. در هر یک از $m$ خط بعدی هم سه عدد آمده که دو سر جاده و وزن آن جاده را مشخص می‌کند. $$1 \le n, m, t_i, w_i \le 1\ 000$$ # خروجی در تنها خط خروجی کمترین زمان برای رسیدن از شهر شماره $1$ به شهر شماره $n$ را چاپ کنید. در صورتی هم که مسیری از شهر $1$ به شهر $n$ وجود نداشته باشد `-1` چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 2 1 1000 1000 1 2 100 2 3 100 ``` ## خروجی نمونه ۱ ``` 101 ``` در این نمونه وقتی که در شهر یک هستیم $99$ بار از قابلیت استفاده می‌کنیم و بعد از آن طول هر دو جاده یک می‌شود. بعد از آن می‌توان بعد از دو ساعت به شهر شماره سه رسید. ## ورودی نمونه ۲ ``` 3 2 3 1 1000 1 2 100 2 3 100 ``` ## خروجی نمونه ۲ ``` 200 ``` در این مثال بدون استفاده از قابلیت می‌توان بعد از $200$ ساعت به شهر $3$ رسید. ## ورودی نمونه ۳ ``` 4 2 1 2 3 4 1 2 5 2 3 10 ``` ## خروجی نمونه ۳ ``` -1 ``` در این نمونه مسیری از شهر $1$ به شهر $4$ وجود ندارد. --------------- <details class="blue"> <summary> راهنمایی ۱ </summary> برای حل این سوال باید الگوریتم [Dijkstra](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) را بلد باشید. </details> <details class="blue"> <summary> راهنمایی ۲ </summary> به مجموعه‌ای از شهر‌ها و جاده‌ها گراف می‌گوییم و منظور از راس همان شهر و از یال همان جاده است. اگر فرض کنید گراف اولیه برابر $G$ باشد. گراف $G_i$ را به این صورت تعریف کنید که راس‌ها و یال‌های آن متنظار با راس‌ها و یال‌های $G$ است ولی طول هر یال آن منهای *i* شده و اگر منفی می‌شد، حذف شده است. می‌توانید مشاهده کنید که $G$ همان $G_0$ است. </details> <details class="blue"> <summary> راهنمایی ۳ </summary> با استفاده از $G_i$‌ها گرافی بسازید که مسئله شما صرفا به مسئله کوتاه ترین مسیر تبدیل شود و پیچیدگی دیگری نداشته باشد. دقت کنید که اگر روی راس *v* در گراف $G_i$‌ باشید می‌توانید در مدت زمان $t_v$ به راس متناظر *v* در گراف $G_{i+1}$ بروید. </details> <details class="blue"> <summary> راهنمایی ۴ </summary> می‌توانید مشاهده کنید که $G_{1001}$ هیچ یالی ندارد چون $w_i \le1\ 000$ </details> <details class="blue"> <summary> راه حل </summary> می‌خواهیم گراف جدیدی بسازیم که از اتصال $G_i$های مخلتف است. به این صورت این گراف را می‌سازیم که برای هر i ($0 \le i \lt 1000$) و هر راس مثل *v* در $G_i$، آن را توسط یک یال یک طرفه با وزن $t_v$ به شهر متناظرش در $G_{i+1}$ وصل می‌کنیم. می‌توانید مشاهده کنید که جواب معادل کوتاه ترین مسیر از شهر 1 در$G_0$ به یکی از شهر‌های *n* در یکی از $G_i$ها است که طول مسیر کمینه شود از طرفی $G_{1001}$ به بعد چون هیچ یالی ندارند نیازی بهشون نداریم پس تعداد راس‌های ما برابر $1001 \times n$ و تعداد یال‌ها حداکثر $1001 \times m$ است که الگوریتم *Dijkstra* می‌تواند جواب مسئله را پیدا کند. </details>