#include <bits/stdc++.h>
#define ii pair <int, long long>
#define x first
#define y second

using namespace std;

const int N = 307;
const int LOG = log2(N) + 7;
const long long oo = 1e18 + 7;

int m, n, a[N][N], SCC, par[N], d[N], p[N][LOG + 10];
long long sum, dist[N];
vector <int> adj[N];

struct edge{
    int u, v, c;
    edge() {}
    edge(int u, int v, int c): u(u), v(v), c(c) {}
}e[N * N];

int Find(int u){
    if (par[u] < 0) return u;
    return par[u] = Find(par[u]);
}

inline void Union(int u, int v){
    if (par[u] > par[v]) swap(u, v);
    par[u] += par[v];
    par[v] = u;
}

void dfs(int u){
    for (int v: adj[u])
        if (!d[v]){
            d[v] = d[u] + 1;
            p[v][0] = u;
            dist[v] = dist[u] + a[u][v];
            dfs(v);
        }
}

inline void Move(int &u, int d){
    int i = 0;
    while (d){
        if (d & 1)
            u = p[u][i];
        d >>= 1; i++;
    }
}

bool cmp(edge a, edge b){
    return a.c < b.c;
}

int LCA(int u, int v){
    if (d[u] < d[v])
        Move(v, d[v] - d[u]);
    else
        Move(u, d[u] - d[v]);
    if (u == v) return u;
    for (int i = LOG; i >= 0; i--){
        if (p[u][i] != p[v][i]){
            u = p[u][i];
            v = p[v][i];
        }
    }
    return p[u][0];
}

int DIST(int u, int v){
    return dist[u] + dist[v] - 2 * dist[LCA(u, v)];
}

struct cmpx{
    bool operator () (ii a, ii b){
        return a.y > b.y;
    }
};

void Dijkstra(int s){
    priority_queue <ii, vector <ii>, cmpx> heap;
    heap.push(ii(s, 0));
    fill(dist, dist + n + 1, oo);
    dist[s] = 0;
    while (heap.size()){
        int u = heap.top().x;
        long long w = heap.top().y;
        heap.pop();
        if (dist[u] != w) continue;
        for (int v: adj[u])
            if (dist[v] > dist[u] + a[u][v]){
                dist[v] = dist[u] + a[u][v];
                heap.push(ii(v, dist[v]));
            }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++){
            cin >> a[i][j];
        }
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++){
            e[++m] = edge(i, j, a[i][j]);
        }
    sort(e + 1, e + m + 1, cmp);
    SCC = n;
    memset(par, -1, sizeof(par));
    for (int i = 1; i <= m; i++){
        int u = Find(e[i].u);
        int v = Find(e[i].v);
        if (u != v){
            Union(u, v);
            adj[e[i].u].push_back(e[i].v);
            adj[e[i].v].push_back(e[i].u);
            SCC--;
            sum += e[i].c;
        }
        if (SCC == 1)
            break;
    }
    d[1] = 1;
    dfs(1);
    for (int j = 1; j <= LOG; j++)
        for (int i = 1; i <= n; i++)
            p[i][j] = p[p[i][j - 1]][j - 1];
    for (int i = 1; i <= m; i++){
        int u = e[i].u;
        int v = e[i].v;
        Dijkstra(u);
        if (e[i].c < dist[v]){
            sum += e[i].c;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        else
            if (e[i].c > dist[v]){
                cout << -1;
                return 0;
            }
    }
    cout << sum;
}


Measured memory_bytes: 1280