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) 106-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).
İlk sətirdə iki tam ədəd n və m (2≤n,m≤106) 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≤a,b≤n) — yol ilə əlaqələndirilmiş şəhərlər;
c (0≤c≤106) — yolun təhlükəliliyi.
Hər hansı iki şəhər bir neçə yol ilə birləşdirilə bilər.
Bir tam ədəd - ən təhlükəsiz marşrutun təhlükəliliyini çap edin.