Pe insula Tortuga sunt N localităţi (numerotate de la 1 la N). Guvernatorul insulei, fostul corsar Ion Vrabie, a hotărât să construiască două megaşcoli moderne, la care vor merge copiii din toate localităţile. Copiii din fiecare localitate urmează să meargă la cea mai apropiată dintre megaşcoli.
Guvernatorul doreşte să selecteze localităţile în care vor fi construite megaşcolile astfel, încât timpul necesar pentru a ajunge la megaşcoală din cea mai îndepărtată localitate să fie cât mai mic posibil.
Funcţionarii au întocmit o hartă a insulei, pe care sunt indicate localităţile şi segmentele de drumuri care unesc unele perechi de localităţi. Pentru fiecare segment de drum care uneşte două localităţi este cunoscut timpul necesar copiilor pentru a ajunge dintr-o localitate în cealaltă. Pentru oricare două localităţi de pe insulă există cel puţin o secvenţă de segmente de drum, care le uneşte.
Notă:
un segment de drum începe la ieşirea dintr-o localitate şi se termină la intrarea în alta. El nu trece prin localităţi intermediare.
Pentru a asigura securitatea copiilor, intersecţiile segmentelor de drum sunt denivelate – nu poţi trece de pe un segment de drum pe altul în afara localităţilor.
Timpul de deplasare în interiorul localităţii se neglijează (se consideră 0)
Timpul de deplasare pe o secvenţă de segmente de drum este egal cu suma timpilor de deplasare pe fiecare segment de drum, inclus în secvenţă.
Cerinţă
Fiind dată harta drumurilor între localităţile insulei, şi durata parcurgerii fiecărui segment de drum, să se scrie un program care să determine localităţile, în care se vor construi megaşcolile.
Date de intrare
Fişierul de intrare megascoala.in conţine pe prima linie numărul natural N. Pe fiecare dintre următoarele N linii se află câte N numere naturale separate prin spaţii, reprezentând elementele unui tablou A de dimensiune N x N.
Elementul A[i,j] al tabloului este:
A[i,j]≠0 : există segmentul de drum, între localităţile i şi j. Timpul de deplasare între localităţi este A[i,j].
A[i,j]=0, i≠j: între localităţile i şi j nu există un segment de drum, care să le unească direct. Drumul din i spre j trece prin localităţi intermediare.
A[i,j]=0, i=j: conform notei b., în interiorul localităţii timpul de deplasare e 0.
Date de ieşire
Fişierul de ieşire megascoala.out va conţine pe prima linie trei numere, separate prin câte un spaţiu reprezentând localităţile în care vor fi amplasate megaşcolile ordonate crescător, respectiv timpul maxim necesar pentru a ajunge la şcoală. Dacă există mai multe posibilităţi de alegere a localităţilor, se va scrie perechea lexicografic minimă.
Restricţii
2 ≤ N ≤ 100
0 ≤ A[i,j] ≤ 32000
Exemple
megascoala.in
megascoala.out
Explicaţie
4
0 3 4 2
3 0 2 5
4 2 0 3
2 5 3 0
1 2 2
(1,2) – din localitatea 3 pleaca in 2 (timpul 2), din localitatea 4 – în 1 (timpul 2). Maxim din (2,2)=2.
Acelaşi rezultat se obţine pentru (1,3), (2,4) şi (3,4), dar soluţiile sunt lexicografic mai mari.
Pentru perechile (1,4) (2,3) se obţine timpul minim 3.