Le strade di Absurdistan#7013
Gli abitanti di Absurdistan hanno imparato a costruire strade solo l'anno scorso. Dopo questa scoperta, ogni città ha deciso di costruire esattamente una strada, che la collega a un'altra città. Ogni strada costruita può essere utilizzata in entrambe le direzioni.
Absurdistan è pieno di sorprendenti coincidenze. Tutte le città hanno impiegato esattamente un anno per costruire le proprie strade. Inoltre, dopo che tutte le strade sono state costruite, è risultato possibile raggiungere qualsiasi città da qualsiasi altra, utilizzando soltanto le nuove strade.
Avete acquistato una guida turistica che non contiene la mappa del paese con le nuove strade. Contiene invece una grande tabella delle distanze minime tra ogni coppia di città, calcolate utilizzando le nuove strade.
Volete determinare quali coppie di città sono collegate da strade e qual è la lunghezza di ciascuna di queste strade. In altre parole, volete ricostruire la mappa delle nuove strade a partire dalla tabella delle distanze minime.
Per ogni test:
La prima riga contiene un numero intero (2 \le n \le 2000) — il numero di città e di strade.
Le successive righe contengono ciascuna numeri interi. Il -esimo numero nella -esima riga è la distanza minima dalla città alla città , utilizzando le nuove strade. La distanza tra due città distinte qualsiasi è positiva e non supera 10^6. La distanza dalla città a se stessa è sempre , e la distanza dalla città alla città coincide con la distanza dalla città alla città .
Per ogni test, stampate righe, ciascuna contenente tre numeri interi , e , a indicare che tra le città e b~(1 \le a, b \le n) esiste una strada di lunghezza c~(1 \le c \le 10^6), dove a \ne b.
Se esistono più soluzioni, stampatene una qualsiasi. Le strade possono essere stampate in qualsiasi ordine. È garantito che esista almeno una soluzione valida.
Stampate una riga vuota tra ciascuna coppia di test consecutivi.
Esempio 1