#include <stdio.h>   
#define inf 100001   
#define fis "rf.in"   
  
using namespace std;   
  
    long ad[300][300],drum[300][300],n,m;   
  
  
void citire()   
{   
    freopen(fis,"r",stdin);   
    scanf("%ld",&n);   
    for (int i=1;i<=n;i++)   
        for (int j=1;j<=n;j++)   
            scanf("%ld",&ad[i][j]);   
    fclose(stdin);   
}   
  
void roy_floyd()   
{   
    for (int k=1;k<=n;k++)   
        for (int i=1;i<=n;i++)   
            for (int j=1;j<=n;j++)   
                if (ad[i][j] > ad[i][k]+ad[k][j] && i!=j)   
                {   
                    ad[i][j]=ad[i][k]+ad[k][j];   
                    drum[i][j]=drum[i][k]+drum[k][j];   
                }   
                else if (ad[i][j] == ad[i][k]+ad[k][j] && drum[i][j] < drum[i][k]+drum[k][j])   
                        drum[i][j]=drum[i][k]+drum[k][j];   
}   
  
void scrie(long ad[300][300])   
{   
    for (int i=1;i<=n;i++)   
    {   
        for (int j=1;j<=n;j++)   
            printf("%ld ",ad[i][j]);   
        printf("\n");   
    }   
}