#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<climits>
#include<string>
#include<iomanip>
#include<sstream>

using namespace std;
using PQelement = pair<int,int>;


void dijkstra(int V,const 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"<<endl;
    for(int i=0;i<V;i++){
        cout<<i<<"\t\t\t";
        
        if(dist[i]==INT_MAX){
        
        }
        cout<<dist[i];
  
    }
    
    
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int V;
    if(!(cin>>V)) return 0;
    
    vector<vector<int>> graph(V,vector<int>(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;
    
    
}