#include<bits/stdc++.h>
using namespace std;
int main(){
    int V;
    cin>>v;
    vector<vector<int>> graph(V,vector<int>(V));
    for(int i=0;i<V;i++){
        for(int j=0;j<V;j++){
            cin>>graph[i][j];
        }
    }
    int scr;
    cin>>scr;
    vector<int> dist(V,INT_MAX)
    vector<bool> visited(V,false);
    dist[scr]=0;
    for(int count=0;count<V-1;count++){
        int u=-1;
        for(int i=0;i<V;i++){
            if(!visited[i] && (u==-1 || dist[i]<dist[u])){
                u=i;
            }
        }
        visited[u]=true;
        for(int v=0;v<V;v++){
            if(graph[u][v] && !visited[v] && dist[u] !=INT_MAX && dist[u]+graph[u][v]<dist[v]){
                dist[v]=dist[u]+graph[u][v];
            }
        }
    }
    cout<<"Vertex\tDistance "<<endl;
    for(int i=0;i<V;i++){
        cout<<i<<"\t\t"<<dist[i]<<"\n";
    }
    return 0;
}