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.

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

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