eolymp
bolt
Try our new interface for solving problems
Məsələlər

Təhlükəli marşrut

Təhlükəli marşrut

Zaman məhdudiyyəti 5 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Bir dövlətdə n şəhər var, bəzi şəhərlər iki tərəfli yollarla birləşdirilmişdir. Şəhərlər 1-dən n-ə qədər tam ədədlərlə nömrələnmişdir. Maliyyə böhranı dövründə dövlətdə cinayətkarlıq səviyyəsi artdı və təşkilatlanmış cinayətkar qruplaşmalar ortaya çıxdı. Buna görə də bəzi yollar səyahət etmək üçün təhlükəli hala gəldi.

Baxə 1-ci şəhərdən n-ci şəhərə getməlidir. O həyatını (və cüzdanını) çox qiymətləndirdiyi üçün, qarətçiləri aldatmaq qərarına gəldi və ən qısa yol olmasa belə, ən az təhlükəli yolu seçməyə qərar verdi. Hər bir yolun təhlükəsini 0-dan (təhlükəsiz) 10^6-ya (çox təhlükəli) qədər tam bir ədəd olaraq təyin etdi. Yolun təhlükəliliyi - marşurutu təşkil edən yolların ən təhlükəlisidir.

Ona ən təhlükəsiz marşrutu seçməkdə kömək edin (yəni, təhlükəliliyinin mümkün qədər minimum olduğu marşrutu).

Giriş verilənləri

İlk sətirdə iki tam ədəd nm~(2 \le n, m \le 10^6) daxil edir. Növbəti m sətirin hər biri bir yolu təyin edir və üç tam ədəddən ibarətdir:

  • a, b~(1 \le a, b \le n) — yol ilə əlaqələndirilmiş şəhərlər;

  • c~(0 \le c \le 10^6) — yolun təhlükəliliyi.

Hər hansı iki şəhər bir neçə yol ilə birləşdirilə bilər.

Çıxış verilənləri

Bir tam ədəd - ən təhlükəsiz marşrutun təhlükəliliyini çap edin.

Nümunə

Giriş verilənləri #1
3 2
1 2 1
2 3 1
Çıxış verilənləri #1
1
Giriş verilənləri #2
6 7
1 2 1
2 3 2
3 4 3
4 6 5
2 6 10
2 5 7
5 6 1

Çıxış verilənləri #2
5