coach

Sunteţi antrenorul ciclistului Adirem Onamihs. În curând va avea loc un eveniment sportiv, iar pentru organizarea acestuia s-au amenajat N intersecţii şi M drumuri bidirecţionale între aceste intersecţii. Pentru fiecare drum se cunoaşte numărul de minute necesare pentru parcurgerea lui. La fiecare intersecţie ciclistul care trece pe acolo este obligat să servească o băutură energizantă şi răcoritoare. Băutura diferă de la intersecţie la intersecţie şi se cunoaşte deja numărul de calorii ale fiecărei băuturi.

Ca mare antrenor, urmează să întocmiţi un plan special pentru a-l antrena pe Adirem. Doriţi ca durata traseului pe care îl alege Adirem să aibă exact T minute, însă nu vreţi să-i plănuiţi întregul traseu (Adirem trebuie să îşi antreneze şi mintea, nu numai corpul). Îi veţi preciza lui Adirem intersecţia de unde îşi începe traseul şi intersecţia unde îl termină. Adirem învaţă repede - el ştie întotdeauna să aleagă traseul optim (drumul cel mai scurt dintre cele două intersecţii). Pentru a-l face să meargă exact T minute îi veţi interzice trecerea prin anumite intersecţii, sub pretextul că valoarea calorică a băuturii servite în intersecţia respectivă nu este benefică pentru antrenamentul lui. Astfel, îi veţi preciza o limită inferioară şi una superioară pentru numărul de calorii ale băuturilor pe care el are voie să le bea. Adirem nu va trece decât prin intersecţiile unde se serveşte o băutură cu valoare calorică între limitele date.

Cerinţă

Scrieţi un program care să calculeze cele patru variabile din antrenamentul lui Adirem: intersecţia de start, intersecţia de finish, valoarea calorică minimă pe care poate să o consume şi valoarea calorică maximă, astfel încât drumul cel mai scurt dintre cele două intersecţii (care să respecte restricţiile) să dureze exact T minute.

Date de intrare

Prima linie a fişierului coach.in conţine trei numere întregi N, M şi T - numărul de intersecţii, numărul de drumuri, respectiv timpul dorit. Următoarele N linii conţin câte un număr - valorile calorice (întregi între 1 şi 10000 inclusiv) ale băuturilor din intersecţii, în ordine (de la 1 la N). Următoarele M linii conţin câte un triplet de numere: două intersecţii (numere distincte între 1 şi N) şi durata drumului dintre ele (întreg între 1 şi 10000 inclusiv).

Date de ieşire

Fişierul coach.out va conţine o linie pe care se vor afla cele patru valori găsite: nodul de start, nodul de finish, valoarea calorică minimă şi valoarea calorică maximă. Nodurile vor fi întregi între 1 şi N, iar valorile calorice vor fi întregi între 1 şi 10000 (inclusiv).

Restricţii şi precizări

• 1 <= N <= 100
• 1 <= M <= 4950
• 1 <= T <= 1000000
• Intersecţiile găsite (de start şi de finish) trebuie să respecte şi ele restricţiile calorice
• O băutură cu valoare calorică x poate fi băută dacă şi numai dacă cmin <= x <= cmax, unde cmin şi cmax sunt valorile calorice minime şi maxime stabilite de antrenor
• Între două intersecţii există maximum un drum
• Valorile calorice sunt distincte
• Există întotdeauna soluţie; dacă există mai multe soluţii se cere oricare dintre ele

Exemplu

coach.in

6 9 11
40
10
20
30
60
50
1 2 2
1 3 2
1 4 4
1 6 10
2 3 3
2 4 1
4 5 1
4 6 5
5 6 2

coach.out

3 6 20 55