#include<iostream>
#include<vector>
#include<climits>
using namespace std;
void findmin(vector<int>&dis,vector<vector<bool>>visited,int v){
    int minval=INT_MAX;
    int minind=-1;
    if(!visited[i] && dis[i]>minval){
        minval=dis[i];
        minind=i;
    }
    return minind;
}
bool solve(vector<vector<int>>&graph,int src,int v){
    vector<int>dis(v,INT_MAX);
    vector<bool>visited(v,false);
    dis[src]=0;
    for(count=0;count<v;count++){
        int u=findmin(dis,visited,v);
        if(u==-1){
            break;
        }
        visited[u]=true;
        if(!visited[i] && graph[u][i]!=0 && graph[u]!=INT_MAX && dis[i]>dis[u]+grapg[u][i]){
            dis[i]=dis[u]+grapg[u][i];
        }
    }
    for(int i=0;i<v;i++){
    cout<<i<<"to"<<dis[i]<<" ";
    }
}
int main(){
    int v;
    cin>>v;
    vector<vector<int>>graph(v,vector<int>(v,0));
    for(int i=0;i<v;i++){
        for(int j=0;j<v;j++){
            cin>>graph[i][j];
        }
    }
    int src;
    cin>>src;
    solve(graph,src,v);
    return 0;
}