CSES - Nettiyhteys
  • Time limit: 1.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? Huomaa, että tietoa voi kulkea samaan aikaan monta kautta Maijalle.

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 aa, bb ja cc. Tämä tarkoittaa, että koneesta aa pystyy lähettämään koneeseen bb sekunnissa cc 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
  • 1m10001 \le m \le 1000
  • 1a,bn1 \le a, b \le n
  • 1c1091 \le c \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