#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#include <assert.h>

// KSP 27-2-6: Testování odezvy
//
// formát vstupu
// • na prvním řádku počet vrcholů N (celé číslo)
// • na dalších N řádcích matice A
// 	• i-tém z nich i-tý řádek matice (mezerami oddělených N celých čísel)
//
// formát výstupu
// • „strom neexistuje“, pokud strom neexistuje, jinak…
// • nalezený strom reprezentovaný seznamem sousedů ve formátu:
// 	• na prvním řádku počet vrcholů N
// 	• na dalších N řádcích seznamy sousedů jednotlivých vrcholů:
// 		• pořadové číslo vrcholu (číslováno od nuly)
// 		• v kulatých závorkách počet sousedů
// 		• dvojtečka, mezera
// 		• mezerami oddělovaný seznam čísel sousedů
//
// Pozn.: Čísla vrcholů stromu na výstupu odpovídají indexům v původní matici,
// ve které je také možné dohledat původní ohodnocení hran, které na výstupu
// chybí.
//
// XXX: Předpokládá se korektní vstup a neošetřuje se hromada možných chybných
// návratů z funkcí vstupu a výstupu. Je to tak mnohem čitelnější při zachování
// rozumné funkčnosti.

// velikost bufferu na řádek vstupu (v bytech)
#define BUF_SIZE 4096
// string vypsaný na stdout, pokud hledaný strom neexistuje
#define NONEXISTENT "strom neexistuje"

// ID vrcholu
typedef int vertex;
// váha hrany nebo množiny hran
typedef int weight;

// čtvercová matice
// • size = délka hrany matice
// • data = položky matice uložené po řádcích
//   (a u symetrické matice je to stejně jedno, rozměry jde prohodit)
typedef struct { int size; weight *data; } matrix;
#define M_GET(mat, row, column) (mat.data[(row) * mat.size + (column)])

// odkazy na předka
// • reprezentace zakořeněného stromu
// • pole indexované číslem vrcholu
// • Předek -1 znamená, že vrchol je kořen.
typedef struct { int size; vertex *data; } parent_links;

// seznam sousedů
// • size = počet vrcholů reprezentovaného grafu
// • index = indexy do data, na kterých začínají jednotlivé seznamy sousedů
//   (poslední položka ukazuje těsně za poslední seznam)
// • data = seznamy sousedů vrcholů, ukládané jeden za druhý
typedef struct { int size; int *index; vertex *data; } adj_list;
#define AL_GET(adj_l, vert, nbr_no) (adj_l.data[adj_l.index[(vert)] + (nbr_no)])
#define AL_SET(adj_l, vert, nbr_no, nbr) (AL_GET((adj_l), (vert), (nbr_no)) = (nbr))
#define AL_NEIGHBORS_CNT(adj_l, vert) (adj_l.index[(vert)+1] - adj_l.index[(vert)])

// Naalokuje a ze zadaného streamu přečte matici, kterou vrací.
char buffer[BUF_SIZE];
matrix read_matrix(FILE *stream) {
	matrix m;
	fgets(buffer, BUF_SIZE, stream);
	sscanf(buffer, "%d", &m.size);
	m.data = malloc(m.size * m.size * sizeof(weight));
	for (vertex u = 0; u < m.size; u++) {
		fgets(buffer, BUF_SIZE, stream);
		int offset = 0;
		for (vertex v = 0; v < m.size; v++) {
			int used;
			sscanf(buffer + offset, "%d%n", &M_GET(m, u, v), &used);
			offset += used;
		}
	}
	return m;
}

// Kontroluje, jestli matice je antireflexivní, symetrická a až na diagonálu kladná.
bool is_valid_graph(matrix distances) {
	for (vertex u = 0; u < distances.size; u++) {
		for (vertex v = 0; v < u; v++) {
			weight uv = M_GET(distances, u, v);
			if (uv <= 0) {
				fputs("Toto řešení nezvládá nekladné vzdálenosti.\n", stderr);
				return false;
			}
			if (M_GET(distances, v, u) != uv) {
				return false;
			}
		}
		if (M_GET(distances, u, u) != 0) {
			return false;
		}
	}
	return true;
}

// Vrátí minimální kostru grafu daného maticí sousednosti, získanou v podobě
// odkazů na předka Jarníkovým algoritmem. Místo pro ni naalokuje.
// • Začíná z vrcholu 0.
// • Vždycky přidává nejlehčí hranu vedoucí z dosud vytvořené části kostry ven.
// • Pamatuje si pro každý vrchol váhu nejlehčí hrany, která z něj vede do
//   stromu. Rychlé udržování této informace je trik, který sráží časovou
//   složitost naivní implementace Jarníka na O(N²).
parent_links min_span_tree(matrix graph) {
	parent_links parent;
	parent.size = graph.size;
	parent.data = malloc(graph.size * sizeof(vertex));
	bool *in_tree = calloc(graph.size, sizeof(bool)); // inicializované na false
	weight *distance = malloc(graph.size * sizeof(weight));
	for (vertex v = 0; v < graph.size; v++) {
		parent.data[v] = -1;
		distance[v] = INT_MAX; // efektivně „nekonečno“
	}
	vertex v = 0;
	distance[0] = 0;
	while (!in_tree[v]) {
		in_tree[v] = true;
		for (vertex n = 0; n < graph.size; n++) { // sousedi
			if (n == v) { // vrchol není svým sousedem
				continue;
			}
			weight w_vn = M_GET(graph, v, n);
			if (distance[n] > w_vn && !in_tree[n]) {
				parent.data[n] = v;
				distance[n] = w_vn;
			}
		}
		weight dist = INT_MAX;
		v = 0;
		for (vertex next = 0; next < graph.size; next++) {
			if (!in_tree[next] && dist > distance[next]) {
				dist = distance[next];
				v = next;
			}
		}
	}
	free(distance);
	free(in_tree);
	return parent;
}

// Převede graf reprezentovaný odkazy na předka do reprezentace seznamem
// sousedů, který vrátí.
adj_list parents_to_al(parent_links parents) {
	adj_list tree;
	tree.size = parents.size;
	tree.index = calloc(tree.size + 1, sizeof(int)); // samé nuly
	// počty sousedů (counting sort)
	for (vertex v = 0; v < parents.size; v++) {
		if (parents.data[v] == -1) {
			continue;
		}
		tree.index[v]++;
		tree.index[parents.data[v]]++;
	}
	// z počtů sousedů dopočítání indexu (prefixové součty)
	int occupied = 0;
	for (vertex v = 0; v < tree.size; v++) {
		int store = occupied;
		occupied += tree.index[v];
		tree.index[v] = store;
	}
	tree.index[tree.size] = occupied;
	// doplnění konkrétních sousedů (bucket + counting sort)
	assert(occupied == 2 * (tree.size - 1)); // půlhrany
	tree.data = malloc(occupied * sizeof(vertex));
	int *nbr_cnt = calloc(tree.size, sizeof(int)); // samé nuly
	for (vertex v = 0; v < parents.size; v++) {
		if (parents.data[v] == -1) {
			continue;
		}
		AL_SET(tree, v, nbr_cnt[v], parents.data[v]);
		nbr_cnt[v]++;
		AL_SET(tree, parents.data[v], nbr_cnt[parents.data[v]], v);
		nbr_cnt[parents.data[v]]++;
	}
	free(nbr_cnt);
	return tree;
}

// Vrací, jestli je daná matice maticí vzdáleností v daném stromě.
// Na zásobníku je v každém okamžiku cesta do aktuálního kořene (start).
// položka zásobníku
// • v = číslo vrcholu
// • next_nbr = pořadové číslo v seznamu prvního ještě nenavštíveného souseda
// • root_dist = vzdálenost od aktuálního kořene
typedef struct { vertex v; int next_nbr; weight root_dist; } stack_item;
typedef struct { int size; stack_item *data; } stack;
#define S_PEEK(s) (s.data[s.size - 1])
#define S_PUSH(s, si) (s.data[s.size++] = (si))
#define S_POP(s) (s.data[--s.size])
bool distances_equal(adj_list tree, matrix distances) {
	assert(tree.size == distances.size);
	int size = tree.size;
	stack s;
	s.size = 0;
	s.data = malloc(size * sizeof(stack_item));
	bool same = true;
	for (vertex start = 0; start < size; start++) {
		// DFS z vrcholu start (kontroluje start-tý řádek matice
		// distances)
		stack_item root;
		root.v = start;
		root.next_nbr = 0;
		root.root_dist = 0;
		S_PUSH(s, root);
		while (s.size > 0) {
			stack_item cur = S_POP(s);
			if (AL_NEIGHBORS_CNT(tree, cur.v) <= cur.next_nbr) {
				// Došli sousedi, vynořujeme se.
				continue;
			}
			vertex prev = s.size > 0 ? S_PEEK(s).v : -1;
			vertex nbr = AL_GET(tree, cur.v, cur.next_nbr);
			cur.next_nbr++;
			S_PUSH(s, cur);
			if (nbr != prev) { // Zpětnou hranu následovat nechceme.
				// Vrchol nbr byl v tomto průchodu potkán poprvé.
				// Jelikož tree je kostra, měly by tudy
				// projít postupně všechny vrcholy.
				stack_item next;
				next.v = nbr;
				next.next_nbr = 0;
				next.root_dist = cur.root_dist + M_GET(distances, cur.v, nbr);
				S_PUSH(s, next);
				// Sedí vzdálenost nového vrcholu od kořene?
				if (M_GET(distances, start, nbr) != next.root_dist) {
					same = false;
					break;
				}
			}
		}
		if (!same) {
			break;
		}
	}
	free(s.data);
	return same;
}

// Vypíše do daného streamu daný strom ve formátu specifikovaném na začátku
// programu.
void print_tree(adj_list tree, FILE *stream) {
	fprintf(stream, "%d\n", tree.size);
	for (vertex v = 0; v < tree.size; v++) {
		int nc = AL_NEIGHBORS_CNT(tree, v);
		fprintf(stream, "%d(%d):", v, nc);
		for (vertex n = 0; n < nc; n++) {
			fprintf(stream, " %d", AL_GET(tree, v, n));
		}
		fputs("\n", stream);
	}
}

// Vypíše do daného streamu daný strom ve formátu „vrchol → předek\n“.
void print_parents(parent_links tree, FILE *stream) {
	for (vertex v = 0; v < tree.size; v++) {
		fprintf(stream, "%d → %d\n", v, tree.data[v]);
	}
}

// Spustí celý algoritmus.
int main(void) {
	matrix distances = read_matrix(stdin);
	if (is_valid_graph(distances)) {
		parent_links parents = min_span_tree(distances);
		adj_list tree = parents_to_al(parents);
		if (distances_equal(tree, distances)) {
			print_tree(tree, stdout);
			//print_parents(parents, stdout);
		} else {
			puts(NONEXISTENT);
		}
		free(tree.data);
		free(tree.index);
		free(parents.data);
	} else {
		puts(NONEXISTENT);
	}
	free(distances.data);
	return 0;
}