unittest
{
	assert( [ "3", "0 1 3", "1 0 2", "3 2 0" ].parse.expand.solve == 3 );
	assert( [ "3", "0 1 3", "1 0 1", "3 1 0" ].parse.expand.solve == -1 );
	assert( [ "5", "0 21 18 11 28", "21 0 13 10 26", "18 13 0 23 13", "11 10 23 0 17", "28 26 13 17 0" ].parse.expand.solve == 82 );
	assert( [ "3", "0 1000000000 1000000000", "1000000000 0 1000000000", "1000000000 1000000000 0" ].parse.expand.solve == 3000000000 );
}



import std.algorithm;
import std.container;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = input.front.to!( long );
	auto ass = new long[][]( n, n );
	foreach( ref as; ass )
	{
		input.popFront;
		as = input.front.split.to!( long[] );
	}
	return tuple( ass );
}

auto solve( long[][] ass )
{
	auto ans = 0L;
	auto dss = new long[][]( ass.length, ass[ 0 ].length );
	foreach( i, ref ds; dss )
	{
		ds[] = long.max;
		ds[ i ] = 0;
	}
	
	// 小さい順に辺を追加する
	auto queue = heapify!( ( a, b ) => b[ 0 ] < a[ 0 ] )( new Tuple!( long, long, long )[ ass.length * ( ass.length - 1 ) / 2 ], 0 );
	for( auto u = 0L; u < ass.length; u++ )
	{
		for( auto v = u + 1; v < ass[ u ].length; v++ )
		{
			queue.insert( tuple( ass[ u ][ v ], u, v ) );
		}
	}
	while( !queue.empty )
	{
		auto a = queue.front[ 0 ];
		auto u = queue.front[ 1 ];
		auto v = queue.front[ 2 ];
		queue.popFront;
		
		if( dss[ u ][ v ] <= a ) continue;		// 辺を追加しても最短経路が変わらない場合は追加しない
		ans += a;
		dss[ u ][ v ] = a;
		dss[ v ][ u ] = a;
		
		// ワーシャルフロイド法（中継点固定）で最短経路を計算
		warshallfloyd( dss, u );
		warshallfloyd( dss, v );
	}
	
	// 表Aと最短経路が一致するか判定
	foreach( as, ds; lockstep( ass, dss ) )
	{
		if( as != ds ) return -1;
	}
	return ans;
}

// 正負の重み付きグラフの全二点間最短経路探索（ワーシャルフロイド法）
auto warshallfloyd( ref long[][] dss, long p )
{
	foreach( f; 0L .. dss.length )
	{
		foreach( t; 0L .. dss.length )
		{
			if( dss[ f ][ p ] == long.max || dss[ p ][ t ] == long.max ) continue;
			dss[ f ][ t ] = min( dss[ f ][ t ], dss[ f ][ p ] + dss[ p ][ t ] );
		}
	}
	return dss;
}
