Karosai

Karosas Rosas plaukioja tvenkinių sistemoje, sudarytoje iš $N$ 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}$ (be abejo, $h_{i,j} = h_{j,i}$). Karosai gali perplaukti iš tvenkinio $i$ į tvenkinį $j$ tik tuomet, kai vandens lygis tvenkinyje $i$ yra nemažesnis nei $h_{i,j}$.

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

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

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

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

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

Toliau pateikta $M$ eilučių, kuriose aprašytos sujungtų tvenkinių poros. Kiekvienoje iš eilučių pateikta po tris sveikuosius skaičius: $i$, $j$, $h_{i,j}$, kurie žymi, kad tvenkiniai $i$ ir $j$ yra sujungti pertvara, kurios aukštis $h_{i,j}$. ($1 ≤ i < j ≤ N$, taip pat laikykite jog $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 $N$-tąjį tvenkinį.

Duomenys tokie, kad visuomet yra galimas kelias iš tvenkinio $1$ į tvenkinį $N$.

• $1 < N ≤ 1\,000$
• $0 < M ≤ \frac{N(N-1)}{2}$
• $0 < h_{i,j} ≤ 10^9$