#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;

template<class T,class U>constexpr bool chmin(T&a,const U b){if(a<=b)return false;a=b;return true;}
template<class T,class U>constexpr bool chmax(T&a,const U b){if(a>=b)return false;a=b;return true;}
#define bit(n,k) ( (n>>k)&1 )

//デバッグ
template<class T>
void Vout(vector<T> &V){
    cout<<"\nstart\n";
    const int sz=V.size();
    for(int i=0;i<sz;i++){
        cout<<i<<" "<<V[i]<<'\n';
    }
    cout<<"end\n"<<endl;
}

template<class T>
void VPout(vector<T> &V){
    cout<<"\nstart\n";
    const int sz=V.size();
    for(int i=0;i<sz;i++){
        cout<<i<<" "<<V[i].first<<" "<<V[i].second<<'\n';
    }
    cout<<"end\n"<<endl;
}


//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


constexpr int MAX=1<<30;
constexpr ll INF=1LL<<62;
constexpr int MOD=1e9+7;
int dx[]={1,-1,0,0},dy[]={0,0,-1,1};

//__builtin_popcount(S);
//#define int ll
//vector<vector<int>> data(3, vector<int>(4));
//vector.resize(a,vector<int>(b,-1));
//vector<vector<vector<要素の型>>> 変数名(要素数1, vector<vector<要素の型>>(要素数2, vector<要素の型>(要素数3, 初期値)));

template<class T>
struct WarshallFloyd{
    int n;
    T inf;
    vector<vector<T>> table;

    inline WarshallFloyd(int n):n(n),inf(numeric_limits<T>::max()){
        init();
    }
    inline void init(){
        table.assign(n,vector<T>(n,inf));
    }

    inline void add(const int from,const int to,const T v){
        table[from][to]=v;
    }

    void build(){
        for(int k=0;k<n;k++){
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(table[i][k]==inf || table[k][j]==inf) continue;
                    chmin(table[i][j],table[i][k]+table[k][j]);
                }
            }
        }
    }
    inline T query(const int from,const int to){
        return table[from][to];
    }

    inline void adbuild(const int from,const int to,const T v){
        chmin(table[from][to],v);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(table[i][from]==inf || table[to][j]==inf) continue;
                chmin(table[i][j],table[i][from]+table[to][j]+v);
            }
        }
    }
};



signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
    cout<<fixed<<setprecision(10);

    int n;
    cin>>n;
    WarshallFloyd<ll> d(n);
    priority_queue< tuple<ll,int,int> > que;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            ll a;
            cin>>a;
            if(i>=j) que.emplace(-a,i,j);
        }
    }
    ll ans=0;
    while(!que.empty()){
        auto now=que.top(); que.pop();
        ll v;
        int i,j;
        tie(v,i,j)=now;
        v*=-1;
        if(d.query(i,j)>v){
            ans+=v;
            d.adbuild(i,j,v);
            d.adbuild(j,i,v);
        }else if(d.query(i,j)==v){
            continue;
        }else{
            cout<<-1<<endl;
            return 0;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 2176