Fişierul intrare/ieşire:	coach.in, coach.out	Sursă	ONI 2004
Autor	Radu Berinde	Adăugată de
Timp execuţie pe test	0.175 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	4/5

Coach

Sunteti antrenorul ciclistului Adirem Onamihs care, in ciuda numelui ciudat, este foarte talentat. In curand va avea loc un eveniment sportiv, un prilej foarte bun de a-l antrena pe ciclist. Pentru organizarea evenimentului s-au amenajat N intersectii si M drumuri bidirectionale intre aceste intersectii. Pentru fiecare drum se cunosc numarul de minute necesare pentru parcurgerea lui. La fiecare intersectie ciclistul care trece pe acolo este obligat sa serveasca o bautura energizanta si racoritoare. Bautura difera de la intersectie la intersectie si se cunosc deja numarul de calorii ale fiecarei bauturi.

Ca un mare antrenor, aveti un plan special pentru Adirem. Doriti ca durata traseului pe care il alege Adirem sa aiba exact T ore, insa nu vreti sa-i planuiti intregul traseu (Adirem trebuie sa isi antreneze si mintea, nu numai corpul). Ii veti preciza lui Adirem doar intersectia de unde isi incepe traseul si intersectia unde il termina. Adirem invata repede - el stie intotdeauna sa aleaga traseul optim (drumul cel mai scurt dintre cele doua intersectii). Atunci cum il puteti face sa mearga exact T ore? Dupa cateva portii de creatina, va vine ideea salvatoare: ii veti interzice trecerea prin anumite intersectii, sub pretextul ca valoarea calorica a bauturii servite in intersectia respectiva nu este benefica pentru antrenamentul lui. Astfel, ii veti preciza o limita inferioara si una superioara pentru numarul de calorii ale bauturilor pe care el are voie sa le bea. Adirem nu va trece decat prin intersectiile unde se serveste o bautura cu valoare calorica intre limitele date.

Cum numarul de intersectii este destul de mare, va trebui sa scrieti un program care sa calculeze cele patru variabile in antrenamentul lui Adirem: intersectia de start, intersectia de finish, valoarea calorica minima pe care poate sa o consume si valoarea calorica maxima, astfel incat drumul cel mai scurt dintre cele doua intersectii (care sa respecte restrictiile) sa dureze T ore.

Date de Intrare

Prima linie a fisierului coach.in contine trei numere intregi N, M si T reprezentand numarul de intersectii, drumuri, respectiv timpul dorit. Urmatoarele N linii contin cate un numar - valoarile calorice a bauturilor din intersectii, in ordine (de la 1 la N). Urmatoarele M linii contin cate un triplet de numere: doua intersectii si durata drumului dintre ele.

Date de Iesire

Fiserul coach.out va contine o linie, pe care se vor afla cele patru valori gasite: nodul de start, nodul de finish, valoarea calorica minima si valoarea calorica maxima. Nodurile vor fi intregi intre 1 si N, iar valorile calorice vor fi intregi intre 1 si 10.000 (inclusiv).

Restrictii si precizari

1 ≤ N <= 100, 1 ≤ M ≤ 4.950, 1 ≤ T ≤ 1.000.000
Costurile muchiilor sunt numere intregi intre 1 si 10.000 (inclusiv)
Caloriile bauturilor sunt numere intregi intre 1 si 10.000 (inclusiv)
Intersectiile gasite (de start si de finish) trebuie sa respecte si ele restrictiile calorice
O bautura cu valoarea calorica x poate fi bauta daca si numai daca cmin ≤ x ≤ cmax, unde cmin si cmax sunt valorile calorice minime si maxime gasite
Intre doua intersectii exista maxim un drum
Valorile calorice sunt distincte
Exista intotdeauna solutie