// Plus court chemin - Algorithme de Dijkstra
// Représentation par matrice d'adjacences
#include <bits/stdc++.h>
using namespace std;

// Chercher un sommet de distance minimale pas encore inclus dans le plus court chemin
int minDist(const vector<int> &dist, const vector<bool> &sptSet)
{
	int min = INT_MAX, idx = -1;
	for(size_t i = 0; i < dist.size(); i++)
		if(!sptSet[i] && dist[i] < min)
			min = dist[i], idx = i;
	return idx;
} // minDist()

// Algorithme de Dijkstra
void dijkstra(const vector<vector<int>> &graph, const int src = 0)
{
	int V = graph.size();
	// Tableau des plus petites distances de src à chaque sommet
	vector<int> dist(V, INT_MAX);
	dist[src] = 0;

	vector<bool> sptSet(V, false);

	// Find shortest path for all vertices
	for(int count = 0; count < V - 1; count++)
	{
		// Sommet de distance minimale pas encore traité
		int u = minDist(dist, sptSet);
		if(u == -1)
			break; // aucun sommet valide trouvé

		sptSet[u] = true; // marquer le sommet u comme traité

		// Mettre à jour les distances des voisins du sommet u seulement si le voisin
		// n'est pas déjà dans le chemin ET que sa distance cumulée depuis le sommet source
		// est plus petite que sa distance à date :
		for(int v = 0; v < V; v++)
			if(!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
					&& dist[u] + graph[u][v] < dist[v])
				dist[v] = dist[u] + graph[u][v];
	}

	// Print the constructed distance array
	cout << "Vertex \t Distance from Source\n";
	for(int i = 0; i < V; i++)
		cout << i << " \t\t " << dist[i] << '\n';
} // dijkstra()

int main()
{
	int V = 0;
	cin >> V; // nombre de sommets

	vector<vector<int>> graphe(V, vector<int>(V, 0)); // matrice d'adjacences

	for(int i = 0; i < V; i++)
		for(int j = 0; j < V; j++)
			cin >> graphe[i][j];

	dijkstra(graphe);

	return 0;
} // main()