Šeštadieninė informatikos olimpiadininkų mokykla

Ponas G. dirba turistų gidu. Dabar jam paskirtos pareigos pervežti turistus iš vieno miesto į kitą. Miestus jungia dvipusio eismo keliai. Kiekvieną kelią aptarnauja kokia nors viena autobusų kompanija. O kiekviena kompanija turi apribojimą, kiek daugiausiai keleivių gali vienu metu vežti.

Ponas G. turi žemėlapį, kuriame pavaizduoti miestai ir juos jungiantys keliai. Jis taip pat žino kiekvieną kelią aptarnaujančios autobusų kompanijos ribojimus. Suprantama, kad ne visuomet pavyks visus turistus pervežti iš vieno miesto į kitą vienu ypu. Pavyzdžiui, panagrinėkite tokį septynių miestų ir juos jungiančių kelių žemėlapį. Briaunos vaizduoja kelius, o skaičiai parašyti ant briaunų – kokį didžiausią keleivių kiekį vienu reisu gali pervežti tą kelią aptarnaujanti autobusų kompanija.

Jei ponas G. nori pervežti 99 turistus iš 1 miesto į 7-ąjį, jam reikės ben jau 5 kelionių, nes jis ir pats kiekvieną kartą turi važiuoti. O maršrutas, kuriuo jis turėtų važiuoti, yra: 1 - 2 - 4 - 7.

Tačiau ponui G. sunku pačiam surasti geriausius maršrutus, kurie leistų pervežti visus turistus iš vieno miesto į kitą per kuo mažiau reisų, todėl jis prašo tavo pagalbos.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašyti du sveikieji skaičiai : N () ir R, reiškiantys, atitinkamai, miestų ir juos jungiančių kelių skaičių. Kitose R eilučių pateikiama po tris sveikuosius skaičius: C1, C2 ir P. C1 ir C2 yra miestų numeriai, o P () yra ribojimas, kiek keleivių tą kelią aptarnaujanti autobusų kompanija gali pervežti vienu reisu. Miestų numeriai yra teigiami sveikieji skaičiai nuo 1 iki N. (R + 1)-ojoje eilutėje įrašyti trys sveikieji skaičiai S, D ir T reiškia, atitinkamai, pradžios miesto numerį, miesto, į kurį reikia pervežti turistus, numerį ir turistų skaičių ().

Rezultatai

Į rezultatų failą jūsų programa turi įrašyti vieną sveikąjį skaičių – kiek mažiausiai reisų ponui G. pakaks visiems turistams pervežti.

Pavyzdys

(Atitinka sąlygos pavyzdį.)

7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 7 99

5