#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<iomanip>
#include<sstream>
#include<climits>
using namespace std;

using PQelement =pair<int,int>;

void dijkstra(int V,vector<vector<int>>& graph,int source){
    
    vector<int> dist(V,INT_MAX);
    
    priority_queue<PQelement,vector<PQelement>,greater<PQelement>> pq;
    
    dist[source]=0;
    pq.push({0,source});
    
    while(!pq.empty()){
        int d=pq.top().first;
        int u=pq.top().second;
        pq.pop();
        if(d<dist[u]){
            continue;
        }
        
        for(int v=0;v<V;++v)
        {
            int weight=graph[u][v];
            if(weight>0 && dist[u]!=INT_MAX){
                if(dist[u]+weight<dist[v]){
                    dist[v]=dist[u]+weight;
                    pq.push({dist[V],v});
                }
            }
            
        }
        
    }
    cout<<"Vertex\tdistance from source";
    for(int i=0;i<V;++1){
        cout<<i<<"\t\t\t ";
        
        if(dist[i]==INT_MAX){
        
        }
        cout<<dist[i]<<endl;
    }
    
    
}
int main(){
    ios_base::sync_with-stdio(false);
    cin.tie(false);
    
    int V;
    if(!(cin>>V)) return 0;
    
    vector<vector<int>> graph(V,vector(V));
    for(int i=0;i<V;++i){
        for(int j=0;j<V;++J){
            if(!(cin>>graph[i][j])) return 0{
                
            }
        }
    }
    int source;
    if(!(cin>>source)) return 0;
    if(source<0 || source>=V || V==0){
        return 0;
    }
    dijkstra(V,graph,source);
    return 0;
    
}