Fişierul intrare/ieşire:	copsamica.in, copsamica.out	Sursă	Lot Râmnicu Vâlcea 2015 - Baraj 3 Seniori
Autor	Adrian Budau, Vlad Gavrila	Adăugată de	Tatomir Alex •atatomir
Timp execuţie pe test	0.5 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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 ≤ 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 (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)).

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.

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

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

Exemplu

Cum se trimit solutii?