- Time limit: 1.00 s
- Memory limit: 128 MB
Tehtäväsi on selvittää, mikä on suurin mahdollinen paino veturille, jolla voi ajaa minkä tahansa kahden aseman välin.
Syöte
Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $m$: asemien määrä ja rataosuuksien määrä. Asemat on numeroitu $1,2,\ldots,n$.
Sitten syötteessä on $m$ riviä, jotka kuvaavat rataosuudet. Jokaisella rivillä on kolme kokonaislukua $a$, $b$ ja $c$: asemien $a$ ja $b$ välillä on rataosuus, jonka maksimipaino on $c$.
Mikään rataosuus ei johda asemasta itseensä, ja kahden aseman välillä on enintään yksi rataosuus. Voit myös olettaa, että on olemassa reitti minkä tahansa kahden aseman välillä.
Tuloste
Tulosta yksi kokonaisluku: painavin veturi, jolla voi ajaa minkä tahansa kahden aseman välillä.
Rajat
- $1 \le n \le 10^5$
- $1 \le m \le 2 \cdot 10^5$
- $1 \le a,b \le n$
- $1 \le c \le 10^9$
Syöte:
5 6
1 2 3
2 3 5
2 4 2
3 4 8
5 1 7
5 4 4
Tuloste:
4