////////////////////////////////////////
//AtCoder Beginner Contest 074
//D - Restoring Road Network
//
//
////////////////////////////////////////
#include <cstring>
#include <iostream>
#include <algorithm> // next_permutation
#include <iomanip>
#include <cmath>
#include <vector>
#include <sstream>
#include <string>
#include <cstdio>
#include <stack>
#include <queue>
#include <list>
#include <numeric> //accumulate
//#include <unordered_map> //ハッシュ関数
#include <fstream> //ifstream, ofstream


using namespace std;

//デバッグ時はTESTを定義する。本番時はこの行をコメントアウトする
#define TEST //*******************************************************************************************************************************************
//そうすることで、以下に定義する、デバッグ時にのみ標準出力する、doutコマンドが実現できる。本番時はダミーストリームに出力
//ただダミーストリームに出力する処理も結構CPU時間食うようなので、TLEを引き起こす原因になる可能性には注意
#ifdef TEST
#define dout cout
#else
stringstream dummy; //デバッグ時のdoutコマンドのダミー出力先
#define dout dummy.str(""); dummy.clear(stringstream::goodbit); dummy //dummyを毎回リセットしておかないとメモリ溢れちゃう。
//どうせ表示しないからgoodbitしなくていいけど、表示する場合はこれしておかないとバグるらしいので、勉強のために。詳しくは http://d.hatena.ne.jp/linden/20060427/p1
#endif

//標準出力先をテキストファイルにしたい場合はOUTPUT2TEXTFILEを定義する。本番時はこの行をコメントアウトする
//#define OUTPUT2TEXTFILE //*******************************************************************************************************************************************
#ifdef OUTPUT2TEXTFILE
#define dout outputfile //というのはTLE問題でどうせdoutを全部コメントアウトしなくちゃいけなくなるので上記方式は却下して、代わりに出力先を標準出力からファイルに切り替えできるようにする
//TESTが定義されていると、outputfileに出力するようになる
#define OUTPUTFILENAME "output.txt"
ofstream outputfile(OUTPUTFILENAME);
#define OutputFilePath "/Users/Nag/Documents/Prgm/Test/DerivedData/Test/Build/Products/Debug/output.txt"
#endif



#define disp(A) dout << #A << " = " << (A) << endl
#define disP(A) dout << (A) << " "
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)

#define dispAll(A,n) dout << #A << " = "; rep(j, 0, (n)) {disP(A[j]);} dout << endl


const int INF = 2e9-1;



int main(){
    int ans = 0;
    
    int n;
    cin >> n;
    
    int a[n][n]; //入力される表
    rep(i,0,n) {
        rep(j,0,n) {
            cin >> a[i][j];
        }
    }
    
//    //test display
//    rep(i,0,n) {
//        disP(i); dispAll(a[i], n);
//    }
//    dout << endl;
    
    int e[n][n]; //辺情報
    memcpy(e, a, sizeof(e)); //aの情報をそのまま辺情報としてコピー
    
    //Warshall Floyd Algorithm
    int d[n][n]; //ここにeにWFを適用した結果を入れる。aと一致するはず
    memcpy(d, a, sizeof(d)); //aの情報をそのままコピー
    
    rep(k,0,n) {
        rep(i,0,n) {
            rep(j,0,n) {
                if(d[i][j] > d[i][k]+d[k][j]) { //a[][]が最短距離を持っているのであれば、これは起こりえない！
                    ans = -1;
                    k = i = j = n; //全ループをbreakするため
                    break;
                }
                
                if(d[i][j] == d[i][k]+d[k][j] && d[i][k]!=0 && d[k][j]!=0 ) { // i --> j と i --> k --> j がともに最短距離なので、辺ijはなくてもよい
                    e[i][j] = 0;
                }
            }
        }
    }
    
//    //test display
//    rep(i,0,n) {
//        disP(i); dispAll(d[i], n);
//    }
//    dout << endl;
//    
//    
//    //test display
//    rep(i,0,n) {
//        disP(i); dispAll(e[i], n);
//    }
//    dout << endl;
    
    //calc. ans
    long long sum = 0;
    rep(i,0,n) {
        rep(j,0,n) {
            sum += e[i][j];
        }
    }
//    disp(ans);
//    disp(sum);
    
    cout << (ans==-1 ? ans : sum/2) << endl;
    

    
    
#ifdef OUTPUT2TEXTFILE
    outputfile.close();
    cout << "\"" << OutputFilePath << "\"" << endl;
#endif
    
    return 0;
}


Measured memory_bytes: 1280