CSES - Veturit
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Sinulle on annettu rataverkon kuvaus: nn asemaa ja niiden välillä mm 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 nn ja mm: asemien määrä ja rataosuuksien määrä. Asemat on numeroitu 1,2,,n1,2,\ldots,n.

Sitten syötteessä on mm riviä, jotka kuvaavat rataosuudet. Jokaisella rivillä on kolme kokonaislukua aa, bb ja cc: asemien aa ja bb välillä on rataosuus, jonka maksimipaino on cc.

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

  • 1n1051 \le n \le 10^5
  • 1m21051 \le m \le 2 \cdot 10^5
  • 1a,bn1 \le a,b \le n
  • 1c1091 \le c \le 10^9

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