#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void a()
{
    int n, a;
    cin >> n >> a;
    cout << ((n * n) - a) << endl;
}

void b()
{
    int n, k;
    cin >> n >> k;
    int result = 0;
    for(int i = 0; i < n; i++)
    {
        int tempa = 0, tempb = 0;
        int x;
        cin >> x;
        if(abs(k - x) < x){
            result += abs(k - x) * 2;
        }else{
            result += x * 2;
        }
    }
    cout << result << endl;
}

void c()
{

}

void d()
{
    struct union_find_tree {
        vector<int> parent;
        vector<int> rank;

        void init(int n)
        {
            for (int i = 0; i < n; i++)
            {
                parent.push_back(i);
                rank.push_back(0);
            }
        }

        int find(int x)
        {
            if (parent[x] == x)
            {
                return x;
            }
            else
            {
                return parent[x] = find(parent[x]);
            }
        }

        void unite(int x, int y)
        {
            x = find(x);
            y = find(y);

            if (x == y) return;

            if (rank[x] < rank[y])
            {
                parent[x] = y;
            }
            else {
                parent[y] = x;
                if (rank[x] == rank[y]) rank[x]++;
            }
        }

        bool same(int x, int y)
        {
            return find(x) == find(y);
        }
    };
    struct edge
	{
		int start;
		int end;
		int cost;

		bool operator<(edge &e) const {
			return cost < e.cost;
		}
	};
    int n;
    cin >> n;
    vector<vector<int>> a(n);
    vector<edge> edges;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j<n; j++)
        {
            int temp;
            cin >> temp;
            a[i].push_back(temp);
            edge newe = {i, j, temp};
            edges.push_back(newe);
        }
    }
    sort(edges.begin(), edges.end());
    union_find_tree tree;
    tree.init(n);
    vector<vector<int>> dp(n);
    /*for(int i = 0; i < n; i++)
    {
        for(int j = 0; j< n;j++)
        {
            if(i == j)
            {
                dp[i].push_back(0);
            } else{
                dp[i].push_back(1 << 29);
            }
        }
    }*/
    dp = a;
    long long int cost = 0;
    /*for(auto e:edges)
    {
        if(!tree.same(e.start, e.end))
        {
            tree.unite(e.start, e.end);
            cost += e.cost;
            dp[e.start][e.end] = e.cost;
        }
    }*/
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++)
        {
            for(int k = 0; k < n; k++)
            {
                dp[j][k] = min(dp[j][k],dp[j][i] + dp[i][k]);
            }
        }
    }
    for(int i = 0; i < n; i++)
    {
        for(int j =0; j< n; j++)
        {
            if(a[i][j] != dp[i][j]) {
                cout << -1 << endl;
                return;
            }
        }
    }
    for(auto e : edges)
    {
        bool notneed = false;
        for(int i = 0; i < n; i++)
        {
            if(i == e.start || i == e.end) continue;
            if(dp[e.start][e.end] == dp[e.start][i] + dp[i][e.end])
            {
                notneed = true;
            }
        }
        if(!notneed)
        {
            cost += e.cost;
        }
    }
    cout << (cost / 2) << endl;
}

int main() {
    d();
    return 0;
}


Measured memory_bytes: 2344