== include(page="template/taskheader" task_id="copsamica") ==

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ş).

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 ≤ i ≤ N) care uneşte cazanele a ~i~ şi b ~i~ poate trece un debit maxim d ~i~ 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.

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 ≤ i ≤ N$) care uneşte cazanele $a{~i~}$ şi $b{~i~}$ poate trece un debit maxim $d{~i~}$ 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 (ai, bi, di) care definesc conductele reţelei, dar a putut să afle pentru fiecare pereche de cazane (x, y) care este debitul maxim dmaxx,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:

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 (t1, t2, ... tk) iar celalalt trece prin conductele (w1, w2, ... w(n-k)), dmax ~x~,y = min(d ~t1~, d ~t2~, ... d ~tk~) + min(d ~w1~, d ~w1~, ... d ~w(n-k)~).

* $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 $(t1, t2, ... tk)$ iar celalalt trece prin conductele $(w1, w2, ... w(n-k))$, dmax{~x,y~} = $min(d{~t1~}, d{~t2~}, ... d{~tk~}) + min(d{~w1~}, d{~w1~}, ... d{~w(n-k)~})$.

h2. Cerinta

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~.

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~}$.

h2. 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~.

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~}$.

h2. 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~.

Î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~}$.

h2. Restricţii

* T = 5
* 3 ≤ N ≤ 1000
* Pentru 60% din teste N ≤ 500
* 1 ≤ dmax ~x,y~ ≤ 20 000
* dmax ~x,y~ = dmax ~y,x~
* Valorile debitelor di afişate trebuie să fie numere naturale ≤ 20 000.
* Cazanele sunt numerotate de la 1.

* $T = 5$
* $3 ≤ N ≤ 1000$
* Pentru $60%$ din teste $N ≤ 500$
* $1 ≤ dmax{~x,y~} ≤ 20 000$
* $dmax{~x,y~} = dmax{~y,x~}$
* Valorile debitelor di afişate trebuie să fie numere naturale ≤ $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.
h2. Exemplu

2 4 2
1 4 1
| 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

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(d1) + min(d2, d3, d4) = 1+1 = 2.
dmax ~2,4~ = min(d2, d3) + min(d1, d4) = 2+1 = 3.

dmax{~1,3~} = min(d1) + min(d2, d3, d4) = 1+1 = 2.
dmax{~2,4~} = min(d2, d3) + min(d1, d4) = 2+1 = 3.

|