#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

const ll MOD = 1e9 + 7;
const ll INF = 1e14;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}
//--------------------------------------------------------------------------------//
struct UnionFind {
private:
    vector<int> par;
    vector<int> count;
    vector<int> rank;

public:
    UnionFind(int N) {
        count.assign(N, 1);
        rank.assign(N, 0);
        par.assign(N, 0);
        rep(i, N) par[i] = i;
    }

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

    void unite(int x, int y) {
        x = root(x), y = root(y);
        if (x == y) return;
        if (rank[x] < rank[y])
            swap(x, y);
        else if (rank[x] == rank[y])
            rank[y]++;
        par[y] = x;
        count[x] += count[y];
        return;
    }

    int size(int x) {
        return count[root(x)];
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }
};
using UF = struct UnionFind;

template <typename T>
vector<T> dijkstra(vector<vector<pair<ll, T>>> &G, ll start){
    using P = pair<T, ll>;
    const T inf = numeric_limits<T>::max();
    ll N = G.size();
    vector<T> dist(N, inf);
    vector<ll> route(N, -1);
    priority_queue<P, vector<P>, greater<P>> pq;
    dist[start] = 0;

    pq.emplace(dist[start], start);
    while(!pq.empty()){
        P p = pq.top();
        pq.pop();
        T c;ll from;
        tie(c, from) = p;
        if (dist[from] < c) continue;
        for(auto& e:G[from]){
            ll to;T cost;
            tie(to,cost) = e;
            if(dist[to]>dist[from]+cost){
                dist[to] = dist[from] + cost;
                route[to] = from;
                pq.emplace(dist[to], to);
            }
        }
    }
    // 各頂点までの最小コスト
    return dist;
    // 始点から各頂点へのルート
    // return route;
}
int main() {
    init();
    ll N;
    cin >> N;
    vvc<ll> A(N, vl(N));
    rep(i, N) rep(j, N) cin >> A[i][j];

    UF uf(N);
    using TU = tuple<ll, ll, ll>;
    priority_queue<TU, vc<TU>, greater<TU>> pq;
    rep(i,N-1)repe(j,i+1,N){
        pq.emplace(A[i][j], i, j);
    }

    vvc<pair<ll, ll>> G(N);
    bool isok = true;
    while(!pq.empty()){
        ll cost, a, b;
        tie(cost, a, b) = pq.top(), pq.pop();
        if(uf.issame(a,b)){
            vl dist = dijkstra(G, a);
            if(dist[b]<cost){
                isok=false;
                break;
            }
            else if(dist[b]>cost){
                G[a].eb(b, cost);
                G[b].eb(a, cost);
                uf.unite(a, b);
            }
        }else{
            G[a].eb(b, cost);
            G[b].eb(a, cost);
            uf.unite(a, b);
        }
    }

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

    ll ans = 0;
    rep(i,N){
        for (auto p : G[i]) ans += p.second;
    }
    cout << ans/2 << endl;
}

Measured memory_bytes: 2680