#include <iostream>

using namespace std;

const int INF = 9999999;

long long n,src;
long long cost[750][750];
long long dist[50005];
long long parent[50005], visited[50005];

void init(){
    int i;
    for(i=1;i<=n;i++)
        {
          dist[i]=INF;
          parent[i]=i;
        }

    dist[src] = 0;
}

int getNearest(){
    int minvalue,minnode,i;
    minvalue = INF;
    minnode = 0;
    for(i=1;i<=n;i++)
        if(dist[i] < minvalue && visited[i] == 0)
            {
                minnode = i;
                minvalue = dist[i];
            }

    return minnode;
}


void dijkstra(){
    int i,nearest,j,l;
    for(j=1;j<=n;j++){
    nearest = getNearest();
    visited[nearest]=1;
    cout<<nearest<<" - ";
    for(i=1;i<=n;i++)
        if(cost[nearest][i]!=INF && dist[i]> cost[nearest][i] + dist[nearest])
            {
            dist[i] = cost[nearest][i] + dist[nearest];
            parent[i] = nearest;
            }
    for(i=1;i<=n;i++)
        cout<<dist[i]<<" ";
    cout<<endl;
    }
}

void print(){
    for(int i=1;i<=n;i++)
        cout<<dist[i]<<" "<<i<<endl;
}

int main()
{
    int i,j,m;
    int a,b,c;
    cin>>n;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            cin>>cost[i][j];

    cin>>src;
    init();
    dijkstra();
    print();
    return 0;
}