- Time limit: 4.00 s
- Memory limit: 128 MB
Voisitko auttaa Uolevia laskemaan maksiminopeuden?
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_i$, $b_i$ ja $c_i$. Tämä tarkoittaa, että koneesta $a_i$ pystyy lähettämään koneeseen $b_i$ sekunnissa $c_i$ 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 200$
- $1 \le a_i, b_i \le n$
- $1 \le c_i \le 10^9$
Syöte:
4 5
1 2 2
1 3 5
2 4 3
3 2 2
3 4 1
Tuloste:
4