==Include(page="template/taskheader" task_id="mine")==

Dupa ce si-a recuperat harta (eventual), Max Damage se gaseste din nou in masina urmarit de politisti. Pentru a scapa se hotaraste sa se ascunda intr-o mina parasita. Problema e ca innauntru este intuneric, iar de la atatea "acrosari" farurile nu mai lumineaza. El pune in functiune un vechi generator de electricitate pentru a lumina galeriile minei, insa acesta functioneaza ciudat si uneori ofera mai multa electricitate, alteori mai putina. Din fericire, Damage stie cum variaza cantitatea de energie electrica. El are de asemenea o harta a minei. Aceasta este formata din galerii care se unesc in intersectii. Intre doua intersectii pot exista oricate galerii, doua galerii nu se intalnesc decat in intersectii, iar o galerie poate fi parcursa in ambele directii. De asemenea Max stie pentru fiecare galerie care trebuie sa fie cantitatea minima de elecricitate produsa de generator pentru a fi parcursa in siguranta. Toate galeriile au aceeasi lungime si pot fi parcurse intr-un singur interval de timp (evident,
daca este destula lumina). Deci tot ce-i trebuie acum este un plan.

Dupa ce si-a recuperat harta, Max Damage se gaseste din nou in masina urmarit de politisti. Pentru a scapa se hotaraste sa se ascunda intr-o mina parasita. Problema e ca inauntru este intuneric, iar de la atatea "acrosari" farurile nu mai lumineaza. El pune in functiune un vechi generator de electricitate pentru a lumina galeriile minei, insa acesta functioneaza ciudat si uneori ofera mai multa electricitate, alteori mai putina. Din fericire, Damage stie cum variaza cantitatea de energie electrica. El are de asemenea o harta a minei. Aceasta este formata din galerii care se unesc in intersectii. Intre doua intersectii pot exista oricate galerii, doua galerii nu se intalnesc decat in intersectii, iar o galerie poate fi parcursa in ambele directii. De asemenea Max stie pentru fiecare galerie care trebuie sa fie cantitatea minima de elecricitate produsa de generator pentru a fi parcursa in siguranta. Toate galeriile au aceeasi lungime si pot fi parcurse intr-un singur interval de timp (evident, daca este destula lumina). Deci tot ce-i trebuie acum este un plan.

h2. Cerinta

Max vrea sa ajunga de la intrarea principala (intersectia numarul $1$) la iesirea de urgenta (intersectia numarul $N$), iar voi va trebui sa ii spuneti cat de repede poate face asta.

Max vrea sa ajunga de la intrarea principala (intersectia numarul $1$) la iesirea de urgenta (intersectia numarul {$N$}), iar voi va trebui sa ii spuneti cat de repede poate face asta.

h2. Date de Intrare

h2. Restrictii si observatii

* $1 ≤ N ≤ 10^4$
* $1 ≤ M ≤ 10^5$
* $1 ≤ W ≤ 10^6$
* capacitatea minima de electricitate pentru o muchie este cuprinsa intre $0$ si $10^9$

* $1 ≤ N ≤ 10^4^$
* $1 ≤ M ≤ 10^5^$
* $1 ≤ W ≤ 10^6^$
* Capacitatea minima de electricitate pentru o muchie este cuprinsa intre $0$ si $10^9^$

* Max Damage poate astepta oricat timp intr-o intersectie
* Daca sirul de $W$ valori se termina, generatorul se opreste si nimeni nu vrea sa ramana intr-o mina parasita pe intuneric (chiar daca ultimele galerii pana la iesire au valoarea $k$ egala cu $0$)
h2. Exemplu

table(example). |_. mine.in |_. mine.out |_. Explicatie |

table(example). |_. mine.in |_. mine.out |

| 3 2
  1 2 5
  2 3 10
  5
  2 6 9 10 0

| 4
| Max ramane la timpul 1 in intersectia 1, la timpul 2 se deplaseaza in intersectia 2, la timpul 3 sta pe loc, iar la timpul 4 se deplaseaza in intersectia 3. |

| 4 |
 
h3. Explicatie
 
Max ramane la timpul 1 in intersectia 1, la timpul 2 se deplaseaza in intersectia 2, la timpul 3 sta pe loc, iar la timpul 4 se deplaseaza in intersectia 3.

==Include(page="template/taskfooter" task_id="mine")==

1098