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 ni în nodul ni + 1 într-un timp mai mic decât timpul în care se poate ajunge din ni în ni + 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~}$.

- 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ă.