Karosai

문제

Karosas Rosas plaukioja tvenkinių sistemoje, sudarytoje iš $NN$ tvenkinių. Kai kurie iš tvenkinių yra sujungti, taigi galima perplaukti iš vieno į kitą. Tačiau juos skiria tam tikro aukščio pertvara, kurią žymėsime $h_{i,j}h\_\{i,j\}$ (be abejo, $h_{i,j}=h_{j,i}h\_\{i,j\}\; =\; h\_\{j,i\}$). Karosai gali perplaukti iš tvenkinio $ii$ į tvenkinį $jj$ tik tuomet, kai vandens lygis tvenkinyje $ii$ yra nemažesnis nei $h_{i,j}h\_\{i,j\}$.

Pavyzdžiui, yra trys tvenkiniai ($N=3N\; =\; 3$), pirmas ir antras tvenkiniai yra sujungti pertvara, kurios aukštis $h_{1,2}=5000h\_\{1,2\}\; =\; 5\backslash ,000$, o antras ir trečias – pertvara, kurios aukštis $h_{2,3}=7000h\_\{2,3\}\; =\; 7\backslash ,000$. Karosai galės perplaukti iš pirmo tvenkinio į antrą, jeigu vandens lygis pirmame (taigi ir antrame) tvenkinyje sieks bent $50005\backslash ,000$. Tačiau, jie galėtų perplaukti iš pirmo į trečią tvenkinį, tik jei vandens lygis sieks $70007\backslash ,000$.

[이미지 1]

Karosai gali perplaukti iš pirmojo į antrąjį tvenkinį, bet ne į trečiąjį.

Karosas Rosas yra apsistojęs $11$-ame tvenkinyje, o jo draugas – tvenkinyje nr. $NN$. Rosui rūpi, koks turi būti vandens lygis $11$-ame tvenkinyje, kad jis galėtų aplankyti savo draugą.

Duota tvenkinių konfigūracija. Raskite, kiek mažiausiai turi būti pakeltas vandens lygis $11$-ame tvenkinyje, kad iš jo būtų įmanoma pasiekti $NN$-tąjį tvenkinį.

입력

Pirmoje eilutėje įrašyti du sveikieji skaičiai: tvenkinių skaičius $NN$ bei sujungtų tvenkinių porų skaičius $MM$.

Toliau pateikta $MM$ eilučių, kuriose aprašytos sujungtų tvenkinių poros. Kiekvienoje iš eilučių pateikta po tris sveikuosius skaičius: $ii$, $jj$, $h_{i,j}h\_\{i,j\}$, kurie žymi, kad tvenkiniai $ii$ ir $jj$ yra sujungti pertvara, kurios aukštis $h_{i,j}h\_\{i,j\}$. (1 &le; i < j &le; N, taip pat laikykite jog $h_{i,j}=h_{j,i}h\_\{i,j\}\; =\; h\_\{j,i\}$).

출력

Išveskite vienintelį sveikąjį skaičių – minimalų vandens lygį pirmajame tvenkinyje, kuris būtinas, kad iš jo būtų galima pasiekti $NN$-tąjį tvenkinį.

Duomenys tokie, kad visuomet yra galimas kelias iš tvenkinio $11$ į tvenkinį $NN$.