Vasile a analizat harta CFR si a identificat N statii de cale ferata (pe care le-a numerotat de la 1 la N) si P tronsoane de cale ferata. Un tronson realizeaza legatura bidirectionala intre doua statii, lungimea unui tronson fiind egala cu timpul necesar trenului sa ajunga dintr-o statie in cealalta.

Initial (secunda 1) Vasile se afla in statia cu numarul 1. Vasile pleaca din statia 1 si trebuie sa se intoarca in statia 1 in intervalul de timp [T1, T2], timpii T1 si T2 fiind exprimati in secunde. El se deplaseaza numai cu trenul, poate cobori din tren in orice statie prin care trece trenul respectiv, se poate urca intr-un tren in oricare dintre statiile prin care trece trenul respectiv (cu conditia ca Vasile sa se afle in statie la momentul in care trenul soseste).

Scrieti un program care sa determine timpul total minim de asteptare in statii, in conditiile in care Vasile trebuie sa calatoreasca cu trenurile existente si sa revina in statia 1 in intervalul de timp [T1, T2].

Fisierul de intrare homeless.in contine:
- pe prima linie 5 numere intregi N P V T1 T2, separate prin spatii (N reprezinta numarul de statii, P este numarul de tronsoane, V este numarul de trenuri, iar T1 si T2 au semnificatia din enuntul problemei).
- fiecare dintre urmatoarele P linii contine informatii despre un tronson sub forma a 3 numere intregi separate prin spatii S1 S2 T cu semnificatia "tronsonul leaga statiile S1 si S2, durata calatoriei pe acest tronson fiind T secunde".
- fiecare dintre urmatoarele V linii contine informatii despre un tren. Primul numar de pe linia corespunzatoare unui tren este T0, care reprezinta timpul de plecare a trenului din prima statie (exprimat in secunde), al doilea numar este NS care reprezinta numarul de statii de pe ruta acestui tren (inclusiv statia de plecare si cea de sosire), iar urmatoarele NS numere reprezinta in ordine numerele statiilor prin care trece trenul. Trenul pleaca de la prima statie si se opreste la ultima statie de pe ruta sa, iar la ultima statie toti calatorii trebuie sa coboare. Toate numerele de pe linie sunt separate prin câte un spatiu.

Fisierul de iesire homeless.out va contine o singura linie pe care va fi scris timpul total minim de asteptare in statii.

1 < N, V < 1001
0<T1<=T2<=50000
0<durata calatoriei pe orice tronson T<601
0<numarul de statii de pe ruta oricarui tren NS<1001

Exemplu

Timp maxim de executie pe test: 2 secunde

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi
Contact: ema at mail.dntis.ro