- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
در کشور(!) شلمرود، \(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\) وجود ندارد.