#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PI 3.141592653589793
#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, a, n) for (int i = a; i < (n); i++)
#define rrep(i, n, k) for (int i = (n); i >= (k); i--);
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T>vector<T> make_vector(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vector(size_t a, Ts... ts){return vector<decltype(make_vector<T>(ts...))>(a, make_vector<T>(ts...));}
const int MOD = 1e9 + 7;
const int INF = 2e18;

template< typename T >
struct edge {
    int src, to;
    T cost;

    edge(int to, T cost) : src(-1), to(to), cost(cost) {}

    edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

    edge &operator=(const int &x) {
        to = x;
        return *this;
    }

    operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

template< typename T >
pair<vector< T >, vector<int>> dijkstra(vector<int> &shortest, WeightedGraph< T > &g, int s) {
    const auto INF = numeric_limits< T >::max();
    vector< T > dist(g.size(), INF);
    set<int> check;
    vector<int> remove;

    using Pi = pair< T, int >;
    priority_queue< Pi, vector< Pi >, greater< Pi > > que;
    dist[s] = 0;
    que.emplace(dist[s], s);
    while(!que.empty()) {
        T cost;
        int idx;
        tie(cost, idx) = que.top();
        que.pop();
        if(dist[idx] < cost) continue;
        for(auto &e : g[idx]) {
            auto next_cost = cost + e.cost;
            if (next_cost == shortest[e.to] && e.src != s) {
                if (check.find(e.to) == check.end()) {
                    remove.push_back(shortest[e.to]);
                    check.insert(e.to);
                }
                // cout << shortest[e.to] << " " << e.src << endl;
            }
            if(dist[e.to] <= next_cost) continue;
            dist[e.to] = next_cost;
            if (shortest[e.to] > dist[e.to] && e.to != s) remove.push_back(-1);
            que.emplace(dist[e.to], e.to);
        }
    }
    return {dist, remove};
}


signed main() {
    int N;
    cin >> N;
    WeightedGraph<int> g(N);
    vector<vector<int>> A(N, vector<int>(N, 0));
    int ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int temp;
            cin >> temp;
            A[i][j] = temp;
            ans += temp;
            if (temp == 0) continue;
            g[i].emplace_back(i, j, temp);
        }
    }
    int minus = 0;
    for (int i = 0; i < N; i++) {
        auto ans = dijkstra(A[i], g, i);
        auto remove = ans.second;
        for (auto temp : remove) {
            if (temp == -1) {
                cout << -1 << endl;
                return 0;
            }
            minus += temp;
        }
    }
    cout << (ans - minus) / 2 << endl;
}


Measured memory_bytes: 4352