Problem 1953: Copșa Mică

După experiențele nefericite avute anul trecut în Las Vegas, Charles a decis să nu mai joace vreodată Blackjack și să-și spele păcatele lucrând la curățarea orașului Copșa Mică, până de curând cel mai poluat oraș din Europa. El va începe prin a curăța instalațiile de producere a negrului de fum (sursa principală a poluării din oraș).

O astfel de rețea este formată din $N$ cazane unite între ele prin $N$ conducte, astfel încât fiecare cazan este unit prin conducte de exact două alte cazane, și se poate ajunge de la un cazan la oricare altul urmând conductele (există exact două moduri de a ajunge de la un cazan la oricare altul). Cu alte cuvinte, rețeaua are forma unui ciclu simplu. Prin fiecare conductă $i, (1 \leq i \leq N)$ care unește cazanele $a_i$ și $b_i$ poate trece un debit maxim di de apă. Un drum de la un cazan $x$ la un alt cazan $y$ este format dintr-o serie conducte adiacente pentru care prima conductă din serie are un capăt în $x$ , iar ultima conductă din serie are un capăt în $y$ .

Din păcate, Charles nu cunoaște tripletele de valori $(a_i, b_i, d_i)$ care definesc conductele rețelei, dar a putut să afle pentru fiecare pereche de cazane $(x, y)$ care este debitul maxim $dmax_{x,y}$ de apă care poate circula de la cazanul $x$ la cazanul $y$ . Astfel, spunem că o rețea produce matricea $dmax_{x,y}$ dacă $dmax_{x,y}$ este egal cu:

$0$ , dacă $x = y$ .
suma debitelor minime aflate pe fiecare din cele două drumuri care unesc cazanele $x$ și $y$ . Mai exact, dacă un drum de la $x$ la $y$ trece prin conductele $(t_1, t_2, ..., t_k)$ iar celalalt trece prin conductele $(w_1, w_2, ... w_{n-k})$ , $dmax_{x,y} = min(d_{t_1}, d_{t_2}, ... d_{t_k}) + min(d_{w_1}, d_{w_2}, ... d_{w_(n-k)})$ .

Cerinţă

Dându-se $N$ și matricea $dmax_{x,y}$ , să se reconstituie o rețea formată din $N$ cazane și $N$ muchii definite prin tripletele de valori $(a_i, b_i, d_i)$ care produce matricea $dmax_{x,y}$ .

Date de intrare

Fişierul de intrare copsamica.in va conține pe prima linie un număr natural $T$ , semnificând numărul de rețele din fișierul de intrare. Pe liniile următoare se vor afla descrierile celor $T$ rețele. O astfel de descriere va conține pe prima linie numărul natural $N$ . Urmează $N-1$ linii, pe linia $x$ aflându-se câte $N-x$ numere naturale separate prin câte un spațiu: al $y$ -lea număr este egal cu valoarea $dmax_{x,x + y}$ .

Date de ieşire

În fişierul de ieşire copsamica.out veți afișa cele $T$ răspunsuri aferente celor $T$ rețele. Răspunsul aferent unei perechi $(N,dmax_{x,y})$ este format din $N$ linii conținând trei numere naturale $a_i, b_i$ și $d_i$ , reprezentând descrierile celor $N$ muchii ce compun o rețea care produce matricea $dmax_{x,y}$ .

Restricţii si precizări

$T = 5$ ;
$3 \leq N \leq 1 \ 000$ ;
Pentru $60%$ din teste $N \leq 500$ ;
$1 \leq dmax_{x,y} \leq 20 \ 000$ ;
$dmax_{x,y} = dmax_{y,x}$
Valorile debitelor $d_i$ afișate trebuie să fie numere naturale $\leq 20 \ 000$ .
Cazanele sunt numerotate de la $1$ .
Exista cel puțin o soluție. În cazul în care există mai multe, puteți afișa oricare dintre ele.

Exemplu

copsamica.in

copsamica.out

Explicație

Pentru prima pereche $(N,dmax_{x,y})$ , putem construi rețeaua circulară formată din muchiile
$a_1 = 1, b_1 = 3, d_1 = 1$
$a_2 = 3, b_2 = 2, d_2 = 2$
$a_3 = 2, b_3 = 4, d_3 = 2$
$a_4 = 1, b_4 = 4, d_4 = 1$
Această rețea produce matricea $dmax_{x,y}$ .
Spre exemplu, $dmax_{1,3} = min(d_1) + min(d_2, d_3, d_4) = 1+1 = 2$ . $dmax_{2,4} = min(d_2, d_3) + min(d_1, d_4) = 2+1 = 3$ .

Copșa Mică