lover

Ion s-a îndragostit de Maria si doreste sa o viziteze cât mai des posibil. Ion locuieste în orasul Iasi, iar Maria locuieste în Lugoj. Ion calatoreste întotdeauna cu masina sa, care consuma 1dl de benzina /km. Rezervorul masinii are o capacitate de K dl. De la Iasi la Lugoj sunt M drumuri diferite si câteva puncte de intersectie notate 1,2,…,N. Iasi, orasul de plecare a fost notat cu 1, iar Lugoj, orasul de sosire a fost notat cu N. În fiecare dintre cele N puncte de intersectie sunt statii de benzina, dar pretul benzinei poate sa difere de la o statie la alta.

Cerinta

Scrieti un program care sa determine cel mai scurt drum de la Iasi la Lugoj si o strategie de a cheltui pe acest drum cât mai putini bani pe benzina.

Date de intrare

Fisierul de intrare se numeste lover.in.

Prima linie a fisierului de intrare contine 3 numere naturale N, M si K. În fiecare dintre urmatoarele M linii se gasesc 3 numere naturale X, Y si D, reprezentând distanta D exprimata în km de la punctul de intersectie X la punctul de intersectie Y. Fiecare din urmatoarele N-1 linii contine un numar natural Pi reprezentand pretul benzinei in statia i.
N M K
X-1 Y1 D1
X2 Y2 D2
...
XM YM DM
P1
P2
...
PN-1

Date de iesire

Fisierul de iesire lover.out are o singura linie pe care afisati, separate prin spatiu, doua numere (lungimea celui mai scurt drum de la Iasi la Lugoj si suma minima cheltuita pe benzina):
lg sum

Restrictii

Exemplu

lover.in

lover.out

4 5 6
1 2 5
1 3 4
3 2 2
2 4 2
3 4 5
5
10
8

7 40

Timp maxim de executie/test: 0.1 secunde

prof. Emanuela Cerchez

Liceul de Informatica "Grigore Moisil" Iasi

Contact: ema@mail.dntis.ro