Războiul dintre Wartia şi Guerrania a ajuns într-un punct critic. Nici o țară nu poate câștiga. Așa că, de comun acord, au hotărât să-și retragă trupele din zona de război. În vederea realizării acestui fapt, toate trupele implicate în conflict au fost regrupate în cele n orașe din zonă, numerotate de la 1 la n. Numai că în timpul luptelor majoritatea drumurilor din zona de conflict au fost distruse, astfel încât deplasarea se poate face pe oricare dintre ele numai într-un singur sens. Desigur, și timpul de deplasare între două orașe între care se mai poate face deplasarea a crescut, dar este cunoscut. Problema comandanților este de a stabili o modalitate de a-și retrage trupele, astfel încât aceasta să fie posibilă și să se poată desfășura cât mai rapid.

Cerinţă

Cunoscându-se numărul de orașe din zona de conflict și harta drumurilor încă utilizabile, să se determine dacă retragerea trupelor se poate face printr-un oraș dat x, oraș în care se găsește un aeroport. În cazul în care acest lucru este posibil, să se determine timpul minim în care toate trupele vor ajunge în acest oraș. Să se determine, de asemenea, un oraș y care permite cea mai rapidă retragere a tuturor trupelor.

Date de intrare

Fișierul de intrare razboi.in va conține pe prima linie două valori naturale, separate printr-un spațiu, n m, reprezentând numărul de orașe, respectiv numărul de drumuri utilizabile. Următoarele m linii conțin fiecare câte trei numere naturale o1 o2 t, separate prin câte un spațiu, indicând un drum utilizabil de la orașul o1 la orașul o2 și timpul de parcurgere t. Ultima linie a fișierului de intrare va conține o valoare naturală x, indicând orașul prin care se dorește să fie realizată retragerea trupelor.

Date de ieşire

Fișierul de ieșire razboi.out va conține pe prima linie o valoare naturală indicând timpul minim în care toate trupele pot ajunge în orașul x. În cazul în care retragerea nu se poate realiza prin orașul x, valoarea afișată va fi 0. Linia a doua a fișierului de ieșire va conține două valori naturale, separate printr-un spațiu, indicând orașul care permite cea mai rapidă retragere și respectiv timpul în care aceasta se poate realiza. În cazul în care există mai multe orașe care permit retragerea în același timp minim, se va afișa cel cu numărul de ordine minim, iar în cazul în care nu există nici un oraș care să permită retragerea trupelor se va afișa valoarea 0 și în acest caz.

Restricţii

0 < n ≤ 501
1 ≤ t ≤ 100
1 ≤ x ≤ n
Drumurile sunt suficient de largi încât să se poată deplasa simultan oricâte trupe pe ele.

Exemple

razboi.in	razboi.out	Explicaţii
5 8 1 2 11 1 3 21 2 4 33 2 5 50 3 4 16 4 5 12 5 1 22 5 3 51 3	88 5 49	Răspunsul e pozitiv (88) și indică faptul retragerea se poate face prin orașul 3: drumul între 1 și 3 este direct cu timp 21 drumul de la 2 la 3 este [2, 4, 5, 1, 3] cu timp 88 drumul de la 4 la 3 este [4, 5, 1, 3] cu timp 55 drumul de la 5 la 3 este [5, 1, 3] cu timp 43 deci ultimii ajung cei din orașul 2. Pentru orașul 5 drumurile și timpii sunt: [1, 3, 4, 5] timp 49 [2, 4, 5] timp 45 [3, 4, 5] timp 28 [4, 5] timp 12

autor: Prof. Marinel Şerban

propunător: Stud. Vlad Manea

FII

vlad.c.manea@gmail.com