시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB222100.000%

문제

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$

예제 입력 1

3 2
1 2 5000
2 3 7000

예제 출력 1

7000

Sąlygoje nagrinėtas pavyzdys.

예제 입력 2

4 5
1 2 5000
1 3 2000
1 4 10000
2 4 4000
3 4 3000

예제 출력 2

3000

Jei pirmame kanale aukštis bus pakeltas iki $3\,000$, tai Rosas galės perplaukti į $3$-iąjį kanalą, o iš ten – į $4$-ąjį.