Greitkelių tinklas

Baitlande sparčiai auga mokamų greitkelių tinklas. Jis tapo toks tankus, kad jau sunku pasirinkti geriausią maršrutą. Greitkelių tinklą sudaro dvikrypčiai miestus jungiantys keliai. Kiekvieną kelią nusako laikas, užtrunkamas kelyje, ir mokestis, kurį reikia sumokėti, norint juo važiuoti.

Maršrutas sudaromas nuosekliai vienas paskui kitą einančių kelių, kuriais reiks važiuoti. Laikas, reikalingas įveikti maršrutą, lygus jį sudarančių kelių laikų sumai. Maršruto mokestis lygi jį sudarančių kelių mokesčių sumai. 

Kuo trumpesnė kelionė ir kuo mažesnė jos kaina, tuo maršrutas geresnis. T.y. vienas maršrutas yra geresnis už kitą, jeigu, juo keliaujant, kelionė trunka trumpiau, o mokėti reikia tiek pat arba mažiau. Kita vertus, maršrutas taip pat yra geresnis, jei mokėti reikia mažiau, o kelionėje užtrunkama tiek pat arba trumpiau. 

Du taškus jungiantį maršrutą vadinsime minimaliu, jeigu nėra geresnio maršruto, jungiančio tuos pačius taškus. Deja, ne visada egzistuoja vienintelis minimalus maršrutas – gali būti keli nepalyginami maršrutai arba maršruto iš viso gali nebūti.

PAVYZDYS
Žemiau esančiame paveiksle pateiktas greitkelių tinklo pavyzdys. Šalia kiekvieno kelio pateikta skaičių pora: mokestis ir kelionės laikas (trukmė).

Panagrinėkime keturis skirtingus maršrutus iš pirmo į ketvirtą miestą: 
•	124;		 (mokestis 4, trukmė 5);
•	134 		(mokestis 4, trukmė 5);
•	1234 	(mokestis 6, trukmė 4)
•	1324 	(mokestis 4, trukmė 10). 

Maršrutai 134 ir 124 yra geresni už 1324. Yra dvi minimalių maršrutų mokesčio-trukmės poros: mokestis 4, trukmė 5 (maršrutai 124 ir 134) ir mokestis 6, trukmė 4 (maršrutas 1234). Rinkdamiesi maršrutą turėsime nuspręsti, ar labiau norėtume keliauti greičiau, bet mokėti brangiau (maršrutas 1234), ar sutiksime daugiau laiko praleisti kelionėje, bet sumokėti mažiau (maršrutas 134 arba 124).

UŽDUOTIS
Parašykite programą, kuri nustatytų kiek egzistuoja skirtingų minimalių maršrutų, jungiančių pradinį ir galinį miestus. Jei dviejų (ar daugiau) maršrutų laikas ir mokestis sutampa, tai jie skaičiuojami kaip vienas maršrutas, t.y. mus domina skirtingos minimalių maršrutų mokesčio–laiko poros, o ne patys maršrutai.

PRADINIAI DUOMENYS
Pirmoje pradinių duomenų bylos bic.in eilutėje įrašyti keturi sveikieji skaičiai: miestų skaičius n (jie numeruojami nuo 1 iki n), 1£n£100, kelių skaičius m, 0£m£300, pradinis ir galinis maršruto miestai s ir e atitinkamai, 1£s,e£n, s¹e. 

Toliau yra m kelius aprašančių eilučių. Vienam keliui skiriama viena eilutė. Kiekvienoje eilutėje įrašyti keturi sveikieji skaičiai: du miestai, kuriuos jungia tas kelias, p ir r, 1£p,r£n, p¹r, važiavimo mokestis c, 0£c£100, ir važiavimo laikas t, 
0£t£100. Du tuos pačius miestus gali jungti daugiau nei vienas kelias.

REZULTATAI
Pirmoje ir vienintelėje rezultatų bylos bic.out eilutėje įrašykite vieną sveikąjį skaičių – skirtingų mokesčio–laiko porų, atitinkančių minimalius maršrutus iš e į s, skaičių.

PRADINIŲ DUOMENŲ IR REZULTATŲ PAVYZDŽIAI

Pradiniai duomenys 		Rezultatai 		Paaiškinimai	

(bic.in)			(bic.out)