== include(page="template/taskheader" task_id="renovare") ==

Populatia orasului Galati a crescut foarte mult in ultimi ani iar infrastructura acestuia nu reuseste sa faca fata la numarul mare de locuitori. Orasul este alimentat cu apa de catre o statie de pompare aflata la cativa kilometri distanta, statie care pompeaza apa printr-o retea de tevi. Tevile sunt conectate intre ele prin rezervoare astfel ca o teava uneste $2$ rezervoare, iar $2$ tevi distincte comunica intre ele daca au un capat in acelasi rezervor. Fiecare teava este caracterizata de $4$ numere: $a$ , $b$ , $c$ , $cst$, avand urmatoarea semnificatie: prin teava respectiva se pot pompa $c$ litri de apa de la rezorvorul $a$ la rezervorul $b$. Daca platim $nr*cst$ lei pentru renovarea tevii atunci vom putea pompa prin ea $c+nr$ litri de apa. Se stie ca rezervorul numarul $1$ reprezinta statia de pompare iar rezervorul numarul $n$ reprezinta rezervorul de la care apa pleaca catre casele din oras. Misiunea dumneavoastra este sa aflati costul minim care trebuie platit pentru ca statia de pompare sa poate trimite catre oras $x$ litri de apa.

Populatia orasului Galati a crescut foarte mult in ultimi ani iar infrastructura acestuia nu reuseste sa faca fata la numarul mare de locuitori. Orasul este alimentat cu apa de catre o statie de pompare aflata la cativa kilometri distanta, statie care pompeaza apa printr-o retea de tevi. Tevile sunt conectate intre ele prin rezervoare astfel ca o teava uneste $2$ rezervoare, iar $2$ tevi distincte comunica intre ele daca au un capat in acelasi rezervor. Fiecare teava este caracterizata de $4$ numere: $a$ , $b$ , $c$ , $cst$ , avand urmatoarea semnificatie: prin teava respectiva se pot pompa $c$ litri de apa de la rezorvorul $a$ la rezervorul $b$. Daca platim $nr*cst$ lei pentru renovarea tevii atunci vom putea pompa prin ea $c+nr$ litri de apa. Se stie ca rezervorul numarul $1$ reprezinta statia de pompare iar rezervorul numarul $n$ reprezinta rezervorul de la care apa pleaca catre casele din oras. Misiunea dumneavoastra este sa aflati costul minim care trebuie platit pentru ca statia de pompare sa poate trimite catre oras $x$ litri de apa.

h2. Date de intrare

h2. Date de iesire

Fisierului $renovare.out$ va contine un singur numar, costul minim care trebuie platit pentru ca reteaua sa poata transporta $x$ litri de apa de la rezervorul $1$ la rezervorul $n$.

Fisierul $renovare.out$ va contine un singur numar, costul minim care trebuie platit pentru ca reteaua sa poata transporta $x$ litri de apa de la rezervorul $1$ la rezervorul $n$.

h2. Restrictii
* $1 ≤ n ≤ 200$
* $1 ≤ m ≤ 2000$

* $1 ≤ x ≤ 200 000$

* Intr-un rezervor nu se poate stoca apa, cantitatea de apa care intra in rezervor trebuie sa fie egala cu cantitatea de apa care iese.
* Capacitatea initiala a tevilor este mai mica sau egala cu $100$
* Costul de renovare a tevilor este mai mic sau egal cu $1000$

* Se garanteaza ca rezultatul va fi mai mic decat $2^32^$

* Se garanteaza ca rezultatul va fi mai mic decat $2*10^9^$

h2. Exemplu

$2*3+3*2+5*2=22$

== include(page="template/taskfooter" task_id="renovare") ==

2104