A fost odata ca niciodata tinutul lui Rosu Imparat, unde traiau Harap-Alb si Ileana Cosanzeana care, fiind indragostiti, se intalneau foarte des desi stateau in orase diferite.
La inceput totul a fost perfect, intrucat Harap-Alb era un tanar destept si stia sa aleaga drumul cel mai scurt pana la casa Ileanei folosind algoritmii invatati la facultate.
Totusi, situatia s-a schimbat de cand imparatul Rosu a decis sa taxeze trecerea prin orase cu un numar de galbeni. Astfel, Fat-Frumos si-a dat seama ca bugetul personal nu ii ajunge intotdeauna daca foloseste cel mai scurt drum pentru a ajunge la Ileana Cosanzeana.
Stiind ca Fat-Frumos stie perfect harta imparatiei data prin N - numarul de orase, si M - numarul de drumuri directe intre orase pe care se poate circula in ambele sensuri, si avand la dispozitie bugetul de care dispune Fat-Frumos pentru a calatori, B, ajutati-l sa descopere cum poate ajunge pana in orasul unde locuieste Ileana Cosanzeaza, t, stiind ca la inceput Fat Frumos este in orasul s. Pentru ca vrea sa o vada pe Ileana cat mai repede, Fat-Frumos prefera sa foloseasca cea mai scurta cale pentru care are bugetul necesar pentru a plati taxele de transport de pe fiecare prin care trece (mai putin sursa, dar incluzand destinatia). Daca exista mai multe astfel de drumuri, evident ca el va prefera drumul cel mai ieftin (care ii lasa cei mai multi bani pentru a iesi in oras cu prietena lui).
Daca sunt mai multe astfel de drumuri ?! (sa vedem daca mai includem asta).
Stiind ca Fat-Frumos stie perfect harta imparatiei data prin $N$ - numarul de orase, si $M$ - numarul de drumuri directe intre orase pe care se poate circula in ambele sensuri, si avand la dispozitie bugetul de care dispune Fat-Frumos pentru a calatori, $B$, ajutati-l sa descopere cum poate ajunge pana in orasul unde locuieste Ileana Cosanzeana, t, stiind ca la inceput Fat Frumos este in orasul s. Pentru ca vrea sa o vada pe Ileana cat mai repede, Fat-Frumos prefera sa foloseasca cea mai scurta cale pentru care are bugetul necesar pentru a plati taxele de transport din fiecare oras prin care trece (mai putin sursa, dar incluzand destinatia). Daca exista mai multe astfel de drumuri, evident ca el va prefera drumul cel mai ieftin pentru ca ii raman mai multi bani pentru a iesi in oras cu prietena lui.
h2. Date de intrare
Fisierul de intrare $drum-bugetat.in$ contine:
* pe primul rand se afla trei numere intregi: N - numarul de orase, M - numarul de drumuri directe intre orase, si B - numarul de galbeni pe care ii are la dispozitie Fat-Frumos
* pe al doilea rand se afla alte doua numere intregi: s - orasul in care se afla Harap-Alb, si t - orasul in care se afla Ileana Cosanzeana
* pe urmatorul rand se afla N numere intregi care reprezinta costurile de trecere (numarul de galbeni care trebuie platiti) prin cele N orase (primul oras apare la inceput, orasul N este ultimul)
* pe urmatoarele M randuri sunt 3 numere: primele doua reprezinta orasele intre care exista acest drum direct, iar al treilea este lungimea drumului respectiv
* pe primul rand se afla trei numere intregi: $N$ - numarul de orase, $M$ - numarul de drumuri directe intre orase, si $B$ - numarul de galbeni pe care ii are la dispozitie Fat-Frumos .
* pe al doilea rand se afla alte doua numere intregi: $s$ - orasul in care se afla Harap-Alb, si $t$ - orasul in care se afla Ileana Cosanzeana.
* pe urmatorul rand se afla $N$ numere intregi care reprezinta costurile de trecere (numarul de galbeni care trebuie platiti) prin cele $N$ orase (primul oras apare la inceput, orasul $N$ este ultimul).
* pe urmatoarele $M$ randuri sunt $3$ numere: primele doua reprezinta orasele intre care exista acest drum direct, iar al treilea este lungimea drumului respectiv.
h2. Date de ieşire
h2. Date de iesire
În fişierul de ieşire $drum-bugetat.out$ scrieti o singura linie care contine urmatoarele 2 numere intregi:
In fisierul de iesire $drum-bugetat.out$ scrieti o linie pe care se afla doua numere intregi separate printr-un spatiu:
* lungimea drumului cel mai scurt care poate fi folosit de Fat-Frumos
* numarul de galbeni pe care Fat-Frumos ii cheltuieste pentru a alege drumul respectiv
h2. Restricţii
h2. Restrictii
* $0 ≤ N ≤ 1000$
* $0 ≤ M ≤ 10000$
* $0 ≤ B ≤ 1000$
* lungimea unui drum direct intre $2$ orase adiacente : $0$ .. $1000$
* taxa pentru a trece printr-un oras: $0$ .. $B$
h2. Exemplu
h2. Observatii
table(example). |_. drum-bugetat.in |_. drum-bugetat.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
* In fisierul de intrare, orasele sunt numerotate de la $1$ la $N$.
* Daca nu exista nici un drum se afiseaza @"-1"@ (fara ghilimele).
h3. Explicaţie
h2. Exemplu
Because of reasons ...
table(example). |_. drum-bugetat.in |_. drum-bugetat.out |
| 7 9 4
1 7
0 1 2 10 1 3 0
1 2 1
1 3 3
2 4 1
2 5 5
3 5 1
3 6 2
4 7 1
5 7 5
6 7 2
| 9 3
|
== include(page="template/taskfooter" task_id="drum-bugetat") ==
