- Time limit: 1.00 s
- Memory limit: 128 MB
Sinulle on annettu rataverkon kuvaus: asemaa ja niiden välillä 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 ja : asemien määrä ja rataosuuksien määrä. Asemat on numeroitu .
Sitten syötteessä on riviä, jotka kuvaavat rataosuudet. Jokaisella rivillä on kolme kokonaislukua , ja : asemien ja välillä on rataosuus, jonka maksimipaino on .
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
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