Məsələlər
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).
\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}
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