CSES - Nettiyhteys
  • Time limit: 4.00 s
  • Memory limit: 128 MB

Uolevin ja Maijan välinen nettiyhteys on toiminut huonosti viime aikoina. Ennen tarkempia tutkimuksia Uolevi haluaisi selvittää, mikä on teoreettinen suurin nopeus, jolla hän voi lähettää tietoa Maijalle verkossa.

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

Esimerkki

Syöte:

4 5
1 2 2
1 3 5
2 4 3
3 2 2
3 4 1

Tuloste:

4