#include <iostream>
using namespace std;

main(){
	int n,a[100][100],i,j,k,mx=0;
	cin>>n;
	for(i=0;i<n;++i)
		for(j=0;j<n;++j){
			cin>>a[i][j];
			if(a[i][j]<0)a[i][j]=1000000000;
		}
	for(k=0;k<n;++k)
		for(i=0;i<n;++i)
			for(j=0;j<n;++j)
				if(a[i][j]>a[i][k]+a[k][j]){
					a[i][j]=a[i][k]+a[k][j];
				}
	k=0;
	for(i=0;i<n;++i)
		for(j=0;j<n;++j)
			if(a[i][j]<1000000000&&a[i][j]>k)
				k=a[i][j];
	cout<<k;
}