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 nn ja mm: verkon koneiden ja yhteyksien määrä. Koneet on numeroitu kokonaisluvuin 1,2,,n1,2,\ldots,n. Kone 1 on Uolevin kone, ja kone nn on Maijan kone.

Tämän jälkeen syötteessä on mm riviä, joista jokainen kuvaa yhden yhteyden. Rivillä on kolme kokonaislukua aia_i, bib_i ja cic_i. Tämä tarkoittaa, että koneesta aia_i pystyy lähettämään koneeseen bib_i sekunnissa cic_i tavua tietoa.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: suurin mahdollinen nopeus (tavua sekunnissa), jolla Uolevi pystyy lähettämään tietoa Maijalle.

Rajat

  • 2n1002 \le n \le 100
  • 1m2001 \le m \le 200
  • 1ai,bin1 \le a_i, b_i \le n
  • 1ci1091 \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