#include <iostream>
#include <fstream>

using namespace std;

static void Dijkstry(int s, int n, int** A, int* dist, int* pred)
{
    int* fin = new int[n];
    int inf=1000000;
    for(int v=0; v<n; v++)
    {
        dist[v]=inf;
        fin[v]=0;
        pred[v]=-1;
    }
    dist[s]=0;
    fin[s]=1;
    int last=s;
    for(int i=1; i<n; i++)
    {
        for(int v=0; v<n; v++)
            if(A[last][v]<inf && fin[v]==0)
            {
                if(dist[last]+A[last][v]<dist[v])
                {
                    dist[v]=dist[last]+A[last][v];
                    pred[v]=last+1;
                }
            }
        int y=0, temp=inf;
        for(int u=0; u<n; u++)
        {
            if((fin[u]==0)&&(dist[u]<temp))
            {
                y=u;
                temp=dist[u];
            }
        }
        if(temp<inf)
        {
            fin[y]=1;
            last=y;
        }
    }
}

int main()
{
    int n, m;
    ifstream wejscie("In0304.txt");
    wejscie >> n >> m;

    int s=m-1;
    cout << n << ' ' << s << endl;

    int** A = new int*[n];
    for(int i=0; i<n; i++)
        A[i] = new int[n];

    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            wejscie >> A[i][j];
    wejscie.close();

    for (int i=0; i<n; i++)
    {
        for (int j=0; j<n; j++)
            cout << A[i][j] << ' ';
        cout << endl;
    }

    int dist[n];
    int pred[n];

    Dijkstry(s, n, A, dist, pred);

    ofstream wyjscie("Out0304.txt");
    wyjscie << "dist[";
    for (int i=0; i<n; i++)
    {
        wyjscie << dist[i];
        if(i<n-1)
            wyjscie << " ";
    }
    wyjscie << ']' << endl << "pred[";
    for (int i=0; i<n; i++)
    {
        wyjscie << pred[i];
        if(i<n-1)
            wyjscie << " ";
    }
    wyjscie << ']';

    wyjscie.close();

    return 0;
}