#include <bits/stdc++.h>

using namespace std;

using ll = long long;

typedef vector<vector<ll> > Matrix; //隣接行列

const ll INF = 1e14;

Matrix dist;

//trueなら負の閉路を検出
bool warshall_floyd(int n) { //nは頂点数
    for (int k = 0; k < n; k++) { //経由点
        for (int i = 0; i < n; i++) { //始点
            for (int j = 0; j < n; j++) { //終点
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    
    //負の閉路を検出
    for (int i = 0; i < n; i++) {
        if (dist[i][i] < 0) return true;
    }
    return false;
}

struct Union_Find {
    //各要素が属する集合の代表(根)を管理する
    //もし、要素xが根であればdata[x]は負の値を取り、-data[x]はxが属する集合の大きさに等しい
    vector<int> data;
    
    Union_Find(int size) : data(size, -1) {}
    bool Union(int x, int y) {
        x = Find(x);
        y = Find(y);
        bool is_union = (x != y);
        if (is_union) {
            if (data[x] > data[y]) swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return is_union;
    }
    int Find(int x) {
        if (data[x] < 0) { //要素xが根である
            return x;
        } else {
            data[x] = Find(data[x]); //data[x]がxの属する集合の根でない場合、根になるよう更新される
            return data[x];
        }
    }
    bool same(int x, int y) {
        return Find(x) == Find(y);
    }
    int size(int x) {
        return -data[Find(x)];
    }
};

struct Edge {
    int u, v;
    ll cost;
    bool operator<(const Edge& e) const {
        return cost < e.cost;
    }
};

struct Graph {
    int n; //頂点数
    vector<Edge> es; //辺集合
    
    int kruskal() {
        sort(es.begin(), es.end());
        Union_Find uf(n);
        int min_cost = 0;
        for(int i = 0; i < (int)es.size(); i++) {
        	Edge e = es[i];
            if (!uf.same(e.u, e.v)) {
                min_cost += e.cost;
                uf.Union(e.u, e.v);
            }
        }
        return min_cost;
    }
};

Graph input() {
   Graph g;
   int m;
   cin >> g.n >> m;
   g.es = vector<Edge>(m);
   for(int i = 0; i < m; i++) {
        cin >> g.es[i].u >> g.es[i].v >> g.es[i].cost;
   }
   return g;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	dist.resize(n, vector<ll>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> dist[i][j];
		}
	}

	Matrix dist2(dist);
	warshall_floyd(n);
	if (dist != dist2) {
		cout << -1 << endl;
		return 0;
	}

	Graph g;
	g.n = n;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			g.es.push_back((Edge){i, j, dist[i][j]});
		}
	}
	sort(g.es.begin(), g.es.end());
	Matrix dist3(n, vector<ll>(n, INF));
	for (int i = 0; i < n; i++) dist3[i][i] = 0;
	long long ans = 0;
	for (Edge& e : g.es) {
		if (dist3[e.u][e.v] > e.cost) {
			ans += e.cost;
			dist3[e.u][e.v] = dist3[e.v][e.u] = e.cost;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (dist3[i][e.u] == INF || dist[e.v][j] == INF) continue;
					dist3[i][j] = min(dist3[i][j], dist3[i][e.u] + dist3[e.u][e.v] + dist3[e.v][j]);
					dist3[j][i] = dist3[i][j];
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3060