#include <bits/stdc++.h>
#include <boost/range/irange.hpp>
#include <boost/range/adaptors.hpp>

using namespace std;
using namespace boost::adaptors;
using uint = unsigned int;
using ll = long long int;
using ull = unsigned long long int;

struct UnionFind {
    vector<ll> data;

    explicit UnionFind(ll size) : data(size, -1) {}

    bool unionSet(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            if (data.at(y) < data.at(x)) swap(x, y);
            data.at(x) += data.at(y);
            data.at(y) = x;
        }
        return x != y;
    }

    bool findSet(ll x, ll y) {
        return root(x) == root(y);
    }

    int root(ll x) {
        return data.at(x) < 0 ? x : data.at(x) = root(data.at(x));
    }

    int size(ll x) {
        return -data.at(root(x));
    }
};

struct Edge {
    ll from;
    ll to;
    ll cost;

    explicit Edge(ll from, ll to, ll cost) : from(from), to(to), cost(cost) {}

    bool operator<(const Edge e) const {
        return cost < e.cost;
    }
};

struct Node {
    ll id;
    vector<pair<ll, ll>> adjacent_edges{}; // (cost, to)
    explicit Node(ll id) : id(id) {}
};

// O(NlogN)
ll dijkstra(vector<Node> &v, ll start_node, ll end_node) {
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<>> pq;
    vector<ll> costs((ll) v.size(), numeric_limits<ll>::max());
    costs.at(start_node) = 0;
    pq.push(make_pair(costs.at(start_node), start_node));
    while (!pq.empty()) {
        ll cost, now;
        tie(cost, now) = pq.top();
        pq.pop();
        for (auto &&p: v.at(now).adjacent_edges) {
            ll c, next;
            tie(c, next) = p;
            ll alt = costs.at(now) + c;
            if (costs.at(next) > alt) {
                costs.at(next) = alt;
                pq.push(make_pair(costs.at(next), next));
            }
        }
    }
    return costs.at(end_node);
}


int main() {
    ll N;
    cin >> N;
    vector<Edge> v{};
    for (auto &&i: boost::irange(0LL, N)) {
        for (auto &&j: boost::irange(0LL, N)) {
            ll a;
            cin >> a;
            if (i > j) {
                v.emplace_back(Edge(i, j, a));
            }
        }
    }
    sort(v.begin(), v.end());
//    for (auto &&i: boost::irange(0LL, (ll) v.size())) {
//        Edge &edge = v.at(i);
//        cout << edge.from << " " << edge.to << " " << edge.cost << endl;
//    }
//    cout << endl;
    vector<Node> nodes;
    for (auto &&i: boost::irange(0LL, N)) {
        nodes.emplace_back(Node(i));
    }
//    O(N^3logN)
    vector<ll> tested{};
    ll cost{0};
    for (auto &&i: boost::irange(0LL, (ll) v.size())) {
        Edge &edge = v.at(i);
        ll cost_now = dijkstra(nodes, edge.from, edge.to);
        if (edge.cost < cost_now) {
//            cout << dijkstra(nodes, edge.from, edge.to) << endl;
            nodes.at(edge.from).adjacent_edges.emplace_back(make_pair(edge.cost, edge.to));
            nodes.at(edge.to).adjacent_edges.emplace_back(make_pair(edge.cost, edge.from));
            cost += edge.cost;
//            cout << edge.from << " " << edge.to << " " << edge.cost << endl;
        } else if (edge.cost > cost_now) {
            cout << -1;
            return 0;
        }
    }
    cout << cost << endl;
    return 0;
}

Measured memory_bytes: 1912