Fişierul intrare/ieşire:	drum-bugetat.in, drum-bugetat.out	Sursă	Adobe - Code Pandas
Autor	Traian Rebedea	Adăugată de	Adobe Romania •adoberomania
Timp execuţie pe test	0.05 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Drum bugetat

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 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.

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.

Date de iesire

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

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

Observatii

• In fisierul de intrare, orasele sunt numerotate de la 1 la N.
• Daca nu exista nici un drum se afiseaza "-1" (fara ghilimele).

Exemplu

Cum se trimit solutii?