==Include(page="template/taskheader" task_id="mine")==
 
==Include(page="template/raw")==
 
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.
 
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.
 
h2. Date de Intrare
 
Din fisierul mine.in se citesc pe prima linie N(numarul de intersectii) si M( numarul de galerii).
Pe urmatoarele M linii se citesc cate 3 numere i j k cu semnificatia ca exista o galerie de la intersectia i la intersectia j iar cantitatea minima de electricitate necesara este k.
Pe linia urmatoare se gaseste W, urmata de W valori. A q-a valoare reprezinta cantitatea de energie electrica generata la momentul q.
 
h2. Date de Iesire
 
In fisierul mine.out se va scrie un singur numar t, timpul minim in care Max poate iesi din mina, sau -1 daca nu are nici o sansa.
 
h2. Restrictii si observatii
 
S 1 <= N <= 10^4
 
S 1 <= M <= 10^5
 
S 1 <= W <= 10^6
 
S capacitatea minima de electricitate pentru o muchie este cuprinsa intre 0 si 10^9
 
S Max Damage poate astepta oricat timp intr-o intersectie
 
S 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

==Include(page="template/taskheader" task_id="mine")==
 
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.
 
h2. Date de Intrare
 
Din fisierul $mine.in$ se citesc pe prima linie $N$(numarul de intersectii) si $M$( numarul de galerii).
Pe urmatoarele $M$ linii se citesc cate $3$ numere $i j k$ cu semnificatia ca exista o galerie de la intersectia $i$ la intersectia $j$ iar cantitatea minima de electricitate necesara este $k$.
Pe linia urmatoare se gaseste $W$, urmata de $W$ valori. A $q-a$ valoare reprezinta cantitatea de energie electrica generata la momentul $q$.
 
h2. Date de Iesire
 
In fisierul $mine.out$ se va scrie un singur numar $t$, timpul minim in care Max poate iesi din mina, sau $-1$ daca nu are nici o sansa.
 
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^$
* 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 |
| 3 2
  1 2 5
  2 3 10
  5
  2 6 9 10 0
| 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")==

mine.in mine.out Explicatie
3 2 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.
1 2 5
2 3 10
5
2 6 9 10 0
==Include(page="template/taskfooter" task_id="mine")==

1098