#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<set>
#include<climits>
#include<cstdlib>
#include<cmath>
#include<string>

using namespace std;

#define INF 1 << 29
#define LL long long int

#define FOR(i,a,b) for(int i=(a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)

struct unionfind{

  unionfind(int n) : par(n) , size(n,1){
    REP(i,n) par[i] = i;
  }

  int root(int x){
    if(par[x] == x) return x;
    return (par[x] = root(par[x]));
  }

  bool find(int x,int y){
    return root(x) == root(y);
  }

  void set(int x,int y){
    x = root(x);
    y = root(y);

    if(x == y)return;

    if(size[x] > size[y]){
      par[y] = par[x];
      size[x] += size[y];
    }else{
      par[x] = par[y];
      size[y] += size[x];
    }

    return;
  }

private:
  vector<int> par;
  vector<int> size;

}typedef UF;

struct edge{
    LL v1;
    LL v2;
    LL cost;
    edge(LL a,LL b,LL c):v1(a),v2(b),cost(c){

    }

    bool operator <(const edge &right)const{
        return cost < right.cost;
    }
};

LL n;
vector<vector<edge>> v;
struct point{
    LL i;
    LL c;
    bool operator >(const point &right)const{
        return c > right.c;
    }
    bool operator <(const point &right)const{
        return c < right.c;
    }
};

LL dijkstra(LL s,LL e){
    vector<bool> close(n+1,false);
    priority_queue<point,vector<point>,greater<point>> pq;
    pq.push(point{s,0});
    while(!pq.empty()){
        point tmp = pq.top();
        pq.pop();
        if(close[tmp.i]){
            continue;
        }
        close[tmp.i] = true;
        if(tmp.i == e){
            return tmp.c;
        }
        for(int i = 0; i < v[tmp.i].size(); i++){
            if(v[tmp.i][i].v1 == tmp.i){
                if(!close[v[tmp.i][i].v2]){
                    pq.push(point{v[tmp.i][i].v2,v[tmp.i][i].cost + tmp.c});
                }
            }else{
                if(!close[v[tmp.i][i].v1]){
                    pq.push(point{v[tmp.i][i].v1,v[tmp.i][i].cost + tmp.c});
                }
            }
        }
    }
    return -1;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> n;
    v = vector<vector<edge>>(n+1);

    vector<vector<LL>> a(n+1,vector<LL>(n+1));

    for(int i = 1; i < n+1; i++){
        for(int j = 1; j < n+1; j++){
            cin >> a[i][j];
        }
    }

    bool frag = true;

    for(int k = 1; k < n+1; k++){
        for(int i = 1; i < n+1; i++){
            for(int j = 1; j < n+1; j++){
                if(a[i][j] > a[i][k] + a[k][j]){
                    frag = false;
                    a[i][j] = a[i][k] + a[k][j];
                }
            }
        }
    }

    if(!frag){
        cout << -1 << endl;
        return 0;
    }

    vector<edge> e;

    for(int i = 1; i < n+1;i++){
        for(int j = i+1; j < n+1; j++){
            if(a[i][j] != 0){
                e.push_back(edge(i,j,a[i][j]));
            }
        }
    }

    sort(e.begin(),e.end());

    LL ans = 0;

    UF u = UF(n+1);

    for(int i = 0; i < e.size(); i++){
        if(u.find(e[i].v1,e[i].v2)){
            LL ret = dijkstra(e[i].v1,e[i].v2);
            if(ret > e[i].cost){
                ans += e[i].cost;
                v[e[i].v1].push_back(edge(e[i].v1,e[i].v2,e[i].cost));
                v[e[i].v2].push_back(edge(e[i].v1,e[i].v2,e[i].cost));
            }
        }else{
            ans += e[i].cost;
            u.set(e[i].v1,e[i].v2);
            v[e[i].v1].push_back(edge(e[i].v1,e[i].v2,e[i].cost));
            v[e[i].v2].push_back(edge(e[i].v1,e[i].v2,e[i].cost));
        }
    }

    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 2680