#include <bits/stdc++.h>
# define NMAX 50000
using namespace std;

int n,s=0,minn=5000,k=0, a[105][105];

void Read()
{
    ifstream fin("date.in");
    ofstream fout("date.out");

    int i, j;
    fin >> n;

    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            fin >> a[i][j];

}

void Roy_Floyd()
{
    int i, j, k;
    for (k = 1; k <= n; k++)
        for (i = 1; i <= n; i++)
            for (j = 1; j <= n; j++)
                if (a[i][j] > a[i][k] + a[k][j])
                    a[i][j] = a[i][k] + a[k][j];
}
void drum(int i,int j)
{
    int k,gasit;
    for(k=1,gasit=0;k<=n && !gasit;k++)
    if(i!=k && j!=k && a[i][j]==a[i][k]+a[k][j])
    {
        drum(i,k);
        drum(k,j);
        gasit=1;
        }
     if(!gasit)
     cout<<j<<" ";
}


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

void Minim()
{

    for(int i=1;i<=n;i++)
     {
      int s=0;
      for(int j=1;j<=n;j++)
      {
          s+=a[i][j];
      }
      a[0][i]=s;
      if(minn>a[0][i])
      {
          minn=a[0][i];
            k=i;}
     }
    cout<<k;
}


int main()
{
    Read();
    Roy_Floyd();
    Write();
    Minim();
    return 0;
}

5
0 5 5000 3 5000
2 0 1 10 16
10 5000 0 5000 7
5000 5000 5000 0 3
5000 1 14 5000 0