#include <iostream>
using namespace std;
 
int main() {
	int  n;
	cin>>n;
	int a[n][n]={};
	for(int i=0; i<n; i++)
		for (int j=0; j<n ; j++){
			cin>>a[i][j];
		}
	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;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oKSB7CglpbnQgIG47CgljaW4+Pm47CglpbnQgYVtuXVtuXT17fTsKCWZvcihpbnQgaT0wOyBpPG47IGkrKykKCQlmb3IgKGludCBqPTA7IGo8biA7IGorKyl7CgkJCWNpbj4+YVtpXVtqXTsKCQl9Cglmb3IgKGludCBrPTA7IGs8bjsgaysrKQoJCWZvcihpbnQgaT0wOyBpPG47IGkrKykKCQkJZm9yIChpbnQgaj0wOyBqPG4gOyBqKyspCgkJCQlhW2ldW2pdPW1pbihhW2ldW2pdLGFbaV1ba10rYVtrXVtqXSk7CglpbnQgbW49MTsKCWZvcihpbnQgaT0wOyBpPG47IGkrKykKCQlmb3IgKGludCBqPTA7IGo8biA7IGorKykKCQkJbW49bWluKG1uLGFbaV1bal0pOwoJZm9yIChpbnQgaT0wOyBpPG47IGkrKyl7CgkJaWYoYVtpXVtpXTwwKSBtbj0tMTsKCX0KCWNvdXQ8PG1uPDxlbmRsOwoJcmV0dXJuIDA7Cn0=

CjMKMCA0MiAxODQ2OCAKNjMzNSAwIDI2NTAxIAoxOTE3MCAxNTcyNSAw

3
0 42 18468 
6335 0 26501 
19170 15725 0