// Arbre de recouvrement minimal (Minimum Spanning Tree)
// Algorithme de Prim
// https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/
#include <bits/stdc++.h>
using namespace std;

// Fonction pour chercher le sommet de plus petite valeur pas encore dans le MST
int minKey(vector<int> &key, vector<bool> &mstSet)
{
	// Initialize min value
	int min = INT_MAX, min_index;

	for(size_t v = 0; v < mstSet.size(); v++)
		if(mstSet[v] == false && key[v] < min)
			min = key[v], min_index = v;

	return min_index;
} // minKey()

// Affichage du MST
void printMST(vector<int> &parent, vector<vector<int>> &graph)
{
	cout << "Edge \tWeight\n";
	for(size_t i = 1; i < graph.size(); i++)
		cout << parent[i] << " - " << i << " \t" << graph[parent[i]][i] << '\n';
} // printMST()

// Construction du MST
void primMST(vector<vector<int>> &graph)
{
	int V = graph.size();

	vector<int> parent(V); // tableau pour le MST

	vector<int> key(V); // tableau des clés minimales

	vector<bool> mstSet(V); // sommets inclus dans le MST

	// Initialiser toutes les clés à "Infini" (INT_MAX)
	for(int i = 0; i < V; i++)
		key[i] = INT_MAX, mstSet[i] = false;

	key[0] = 0; // 1er sommet dans le MST

	parent[0] = -1; // Le 1er sommet est la "racine" du MST (pas de parent)

	for(int count = 0; count < V - 1; count++)
	{
		// Choisir le sommet de clé minimale pas encore dans le MST
		int u = minKey(key, mstSet);

		// L'ajouter au MST
		mstSet[u] = true;

		// Update key value and parent index of
		// the adjacent vertices of the picked vertex.
		// Consider only those vertices which are not
		// yet included in MST
		// On met à jour la clé et le parent des sommets adjacents à u
		// (seulement s'ils ne sont pas déjà dans le MST)
		for(int v = 0; v < V; v++)
		{
			if(graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
				parent[v] = u, key[v] = graph[u][v];
		}
	}

	// Affichage du MST
	printMST(parent, graph);
}

// Programme principal
int main()
{
	int n = 0;
	cin >> n; // nombre de sommets

	vector<vector<int>> graph(n, vector<int>(n, 0)); // matrice d'adjacences
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			cin >> graph[i][j];

	// Construction et affichage du MST
	primMST(graph);

	return 0;
} // main()