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). \InputFile İ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: \begin{itemize} \item $a, b~(1 \le a, b \le n)$ --- yol ilə əlaqələndirilmiş şəhərlər; \item $c~(0 \le c \le 10^6)$ --- yolun təhlükəliliyi. \end{itemize} Hər hansı iki şəhər bir neçə yol ilə birləşdirilə bilər. \OutputFile Bir tam ədəd - ən təhlükəsiz marşrutun təhlükəliliyini çap edin. \includegraphics{https://static.e-olymp.com/content/e3/e38592c669b2f7e2841ee8faf0346f49e807fccb.gif}