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ələr