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

Ai intrat cu maşina într-un graf *orientat* $G$ cu costuri pe muchii. Costul unei muchii denotă lungimea acesteia în kilometri. Momentan te afli în nodul $1$ şi vrei să ajungi în nodul $N$ cât mai repede. Maşina ta are o viteză maximă egală cu $V_max km/h$. Există o limită superioară de viteză în graf, egală cu $LIMIT km/h$. Pentru a verifica respectarea acestei limite, administratorii grafului au plasat camere speciale de trafic în $K$ dintre cele $N$ noduri. Ele funcţionează astfel:

Ai intrat cu maşina într-un graf *orientat* $G$ cu costuri pe muchii. Costul unei muchii denotă lungimea acesteia în kilometri. Momentan te afli în nodul $1$ şi vrei să ajungi în nodul $N$ cât mai repede. Maşina ta are o viteză maximă egală cu $V{~max~} km/h$. Există o limită superioară de viteză în graf, egală cu $LIMIT km/h$. Pentru a verifica respectarea acestei limite, administratorii grafului au plasat camere speciale de trafic în $K$ dintre cele $N$ noduri. Ele funcţionează astfel:

-

- Pentru fiecare nod care conţine o cameră, camera va înregistra toate maşinile care intră în respectivul nod sau care îl părăsesc şi va consemna momentele de timp la care au loc aceste evenimente.
- Dacă o maşină trece prin mai multe noduri cu cameră, fie ele, în ordine, $n{~1~}, n{~2~} .. n{~k~}$, atunci sistemul poate verifica pentru fiecare pereche $n{~i~}, n{~i + 1~}$ dacă maşina respectivă a întrecut limita de viteză în segmentul de drum de la $n{~i~}$ la $n{~i + 1~}$.  Dacă o maşină a ajuns din nodul $n{~i~}$ în nodul $n{~i + 1~}$ într-un timp mai mic decât timpul în care se poate ajunge din $n{~i~} în $n{~i + 1~}$ pe drumul cel mai scurt şi cu viteza LIMIT, atunci sistemul îşi dă seama că maşina respectivă a întrecut limita de viteză. Notaţi că nu este necesar ca nodurile speciale din acest şir să fie singurele noduri din drumul parcurs de maşină. Pot exista oricâte noduri fără camera pe segmentul de drum dintre $n{~i~}$ si $n{~i + 1~}$.
 
Se cere să se afle timpul minim în care se poţi ajunge din nodul $1$ în nodul $N$ fără a fi prins de sistem că ai încălcat limita de viteză.

h2. Date de intrare

Fişierul de intrare $cameras.in$ ...

Pe prima linie a fişierului de intrare se află numerele $N$, $M$ şi $K$, reprezentând numărul nodurilor, numărul muchiilor grafului şi numărul oraşelor în care există o cameră.
A doua linie a fişierului de intrare conţine cele $K$ oraşe în care se află o cameră.
Pe următoarea linie se află valorile $V{~max~}$ şi $LIMIT$.
Pe următoarele $M$ linii se află câte o muchie în forma $from to length$, însemnând că există o muchie unidirecţională de la nodul $from$ la nodul $to$ de lungime $length km$.

h2. Date de ieşire

În fişierul de ieşire $cameras.out$ ...

Pe unica linie a fişierului de ieşire trebuie să se afle timpul minim în care maşina poate ajunge din nodul $1$ în nodul $N$ fără ca sistemul să observe că a întrecut limita de viteză.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $2 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 250.000$
* $1 ≤ K ≤ N$
* $1 ≤ V{~max~}, LIMIT, length ≤ 30.000$, unde $length$ reprezintă lungimea unei muchii. Toate aceste valori sunt numere întregi.
* Se garantează că există cel puţin un drum de la nodul $1$ la nodul $N$.
* Răspunsul dat poate să difere de cel real prin cel mult $10^-9^$

h2. Exemplu
table(example). |_. cameras.in |_. cameras.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4 7 3
2 3 4
10 5
1 2 1
2 4 5
4 1 1
3 2 9
2 3 3
4 3 10
3 4 4
| 1.100000

|

h3. Explicaţie
 
...
 
== include(page="template/taskfooter" task_id="cameras") ==
 

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