Təhlükəli marşrut
Təhlükəli marşrut
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 n və m~(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ə
3 2 1 2 1 2 3 1
1
6 7 1 2 1 2 3 2 3 4 3 4 6 5 2 6 10 2 5 7 5 6 1
5