#include <iostream>
using namespace std;
 
int main() {
	int  n, inf=1e9;
	cin>>n;
	int a[n][n]={};
	for(int i=0; i<n; i++)
		for (int j=0; j<n ; j++){
			cin>>a[i][j];
			if(a[i][j]==0) a[i][j]=inf;
		}
	for (int k=0; k<n; k++)
		for(int i=0; i<n; i++)
			for (int j=0; j<n ; j++)
				a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
	int mn=1;
	for(int i=0; i<n; i++)
		for (int j=0; j<n ; j++)
			mn=min(mn,a[i][j]);
	for (int i=0; i<n; i++){
		if(a[i][i]<0) mn=-1;
	}
	cout<<mn<<endl;
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oKSB7CglpbnQgIG4sIGluZj0xZTk7CgljaW4+Pm47CglpbnQgYVtuXVtuXT17fTsKCWZvcihpbnQgaT0wOyBpPG47IGkrKykKCQlmb3IgKGludCBqPTA7IGo8biA7IGorKyl7CgkJCWNpbj4+YVtpXVtqXTsKCQkJaWYoYVtpXVtqXT09MCkgYVtpXVtqXT1pbmY7CgkJfQoJZm9yIChpbnQgaz0wOyBrPG47IGsrKykKCQlmb3IoaW50IGk9MDsgaTxuOyBpKyspCgkJCWZvciAoaW50IGo9MDsgajxuIDsgaisrKQoJCQkJYVtpXVtqXT1taW4oYVtpXVtqXSxhW2ldW2tdK2Fba11bal0pOwoJaW50IG1uPTE7Cglmb3IoaW50IGk9MDsgaTxuOyBpKyspCgkJZm9yIChpbnQgaj0wOyBqPG4gOyBqKyspCgkJCW1uPW1pbihtbixhW2ldW2pdKTsKCWZvciAoaW50IGk9MDsgaTxuOyBpKyspewoJCWlmKGFbaV1baV08MCkgbW49LTE7Cgl9Cgljb3V0PDxtbjw8ZW5kbDsKCXJldHVybiAwOwp9

CjMKMCA0MiAxODQ2OCAKNjMzNSAwIDI2NTAxIAoxOTE3MCAxNTcyNSAw

3
0 42 18468 
6335 0 26501 
19170 15725 0