#include <iostream>
#include <fstream>
using namespace std;

int n,m,c[100][100],infinit,d[100][100];


void citire()
{
    int x,y,cost;
    ifstream f("graf.txt");
    f>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
    {
        f>>c[i][j];

    }
    f>>infinit;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        if(i!=j && c[i][j]==0)
        c[i][j]=infinit;

}

void drum_initial()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
    {
        if(i!=j && c[i][j]!= infinit)
            d[i][j]=i;
        if(i!=j && c[i][j]==infinit)
            d[i][j]=infinit;
    }
}

void Floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        if(c[i][j]>c[i][k]+c[k][j])
    {
        c[i][j]=c[i][k]+c[j][k];
        d[i][j]=k;
    }
}

void drum(int i, int j)
{
    if(i==j)
        cout<<i<<" ";
    else
    {
        drum(i,d[i][j]);
        cout<<j<<" ";

    }
}

void afisare_standard()
{
    for(int i=1;i<=n;i++)
       {
           for(int j=1;j<=n;j++)
            cout<<c[i][j]<<" ";
           cout<<endl;
}
}

void afisare()
{
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        if(i!=j)
        if(c[i][j]!=infinit)
    {
        cout<<"costul de la "<<i<<" la "<<j<<"  este "<<c[i][j]<<" "<<endl;
        cout<<"drumul este:";
        drum (i,j);
        cout<<endl;

    }
    else cout<<"Nu exista drum de la "<<i<<" la "<<j<<endl;

}

int main()
{
    int i,j,minim=INT_MAX;
    citire();

    drum_initial();

    Floyd();
    int suma[100];
    for(i=1;i<=n;i++)
    {   s[i]=0;
        for(j=1;j<=n;j++)
        if(c[i][j]!=infinit)
        s[i]=s[i]+c[i][j];
        if(s[i]<minim)minim=s[i];
    }
    afisare();
}