#include <bits/stdc++.h>
#define rep(i, n) for (lli i = 0; i < (n); i++)
#define rrep(i, n) for (lli i = (n)-1; i >= 0; i--)
using namespace std;
using lli = long long int;
const int UF_MAX = 500;
struct UFind {
    int par[UF_MAX];
    int rank[UF_MAX];
    int count[UF_MAX];
    UFind(int n)
    {
        rep(i, n)
        {
            par[i] = i;
            rank[i] = 0;
            count[i] = 1;
        }
    }
    int find(int x)
    {
        if (par[x] == x) {
            return x;
        } else {
            return par[x] = find(par[x]);
        }
    }
    void unite(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
            return;
        if (rank[x] < rank[y]) {
            par[x] = y;
            count[y] += count[x];
        } else {
            par[y] = x;
            count[x] += count[y];
            if (rank[x] == rank[y])
                rank[x]++;
        }
    }
    bool same(int x, int y)
    {
        return find(x) == find(y);
    }
};


int main()
{
    int n;
    cin >> n;
    lli d[400][400];
    lli pd[400][400];

    rep(i, n) rep(j, n)
    {
        cin >> d[i][j];
        pd[i][j] = d[i][j];
    }
    rep(k, n)
    {
        rep(i, n) rep(j, n)
        {
            pd[i][j] = min(pd[i][k] + pd[k][j], pd[i][j]);
        }
    }
    bool flag = true;
    rep(i, n) rep(j, n)
    {
        if (pd[i][j] != d[i][j])
            flag = false;
    }
    if (!flag)
        cout << -1 << endl;
    else {
        UFind uf(n);
        using p = pair<lli, pair<lli, lli>>;
        priority_queue<p, vector<p>, greater<p>> que;
        //priority_queue<p> que;

        rep(i, n) rep(j, n) if (i < j) que.push(p(d[i][j], make_pair(i, j)));
        lli ans = 0;
        int cnt = 0;
        lli dist[400][400] = {};
        rep(i, n) rep(j, n) dist[i][j] = 1e10;
        rep(i, n) dist[i][i] = 0;
        while (!que.empty()) {
            auto s = que.top();
            que.pop();
            auto u = s.second.second;
            auto v = s.second.first;
            uf.unite(u, v);
            bool flag = true;
            rep(j, n)
            {
                if (dist[u][j] + dist[j][v] == s.first) {
                    flag = false;
                    break;
                }
            }

            if (flag) {
                ans += s.first;
                dist[u][v] = dist[v][u] = s.first;
                rep(j, n) rep(i, n)
                {
                    dist[i][v] = min(dist[i][v], dist[i][j] + dist[j][v]);
                    dist[i][u] = min(dist[i][u], dist[i][j] + dist[j][u]);
                    dist[v][i] = min(dist[v][i], dist[v][j] + dist[j][i]);
                    dist[u][i] = min(dist[u][i], dist[u][j] + dist[j][i]);
                }
                cnt += 1;
            }
            // rep(i, n)
            // {
            // }
            // if (uf.same(u, v)) {
            //     cout << u << " " << v << endl;
            //     uf.unite(u, v);
            //     dist[u][v] = dist[v][u] = s.first;
            //     cnt++;
            // }
            // if (cnt == n - 1) {
            //     break;
            // }
        }
        /*cout << cnt << endl;
        rep(i, n) rep(j, n)
        {
            cout << dist[i][j] << " ";
            if (j == n - 1)
                cout << endl;
        }
        */

        cout << ans << endl;
    }
}


Measured memory_bytes: 5240