- Time limit: 1.00 s
- Memory limit: 512 MB
Syrjälän tietoverkossa on n konetta ja m yhteyttä. Jokainen yhteys kuvaa, miten nopeasti jokin kone voi lähettää tietoa toiselle koneelle.
Kotivalo haluaa ladata tietoa palvelimelta. Mikä on suurin mahdollinen latausnopeus käyttäen verkossa olevia yhteyksiä?
Syöte
Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja m: koneiden ja yhteyksien määrä. Koneet on numeroitu 1,2,\dots,n Kone 1 on palvelin ja kone n on Kotivalon kone.
Tämän jälkeen tulee m riviä, jotka kuvaavat yhteydet. Jokaisella rivillä on kolme kokonaislukua a, b ja c: kone a voi lähettää tietoa koneelle b nopeudella c.
Tuloste
Tulosta yksi kokonaisluku: maksiminopeus, jolla Kotivalo voi ladata tietoa.
Rajat
- 1 \le n \le 500
- 1 \le m \le 1000
- 1 \le a,b \le n
- 1 \le c \le 10^9
Esimerkki
Syöte:
4 5 1 2 3 2 4 2 1 3 4 3 4 5 4 1 3
Tuloste:
6