- Time limit: 1.00 s
- Memory limit: 128 MB
Voisitko auttaa Uolevia laskemaan maksiminopeuden? Huomaa, että tietoa voi kulkea samaan aikaan monta kautta Maijalle.
Syöte
Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $m$: verkon koneiden ja yhteyksien määrä. Koneet on numeroitu kokonaisluvuin $1,2,\ldots,n$. Kone 1 on Uolevin kone, ja kone $n$ on Maijan kone.
Tämän jälkeen syötteessä on $m$ riviä, joista jokainen kuvaa yhden yhteyden. Rivillä on kolme kokonaislukua $a$, $b$ ja $c$. Tämä tarkoittaa, että koneesta $a$ pystyy lähettämään koneeseen $b$ sekunnissa $c$ tavua tietoa.
Tuloste
Ohjelmasi tulee tulostaa yksi kokonaisluku: suurin mahdollinen nopeus (tavua sekunnissa), jolla Uolevi pystyy lähettämään tietoa Maijalle.
Rajat
- $2 \le n \le 100$
- $1 \le m \le 1000$
- $1 \le a, b \le n$
- $1 \le c \le 10^9$
Syöte:
4 5
1 2 2
1 3 5
2 4 3
3 2 2
3 4 1
Tuloste:
4