Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Veturit

Veturit


View task | Model solution | Statistics


Veturit

Time limit:1.00 s
Memory limit:128 MB

Sinulle on annettu rataverkon kuvaus: $n$ asemaa ja niiden välillä $m$ rataosuutta. Tiedät myös jokaisesta rataosuudesta, mikä on maksimipaino siinä ajavalle veturille.

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$.

Voit 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
Esimerkki

Syöte:
5 6
1 2 3
2 3 5
2 4 2
3 4 8
5 1 7
5 4 4


Tuloste:
4