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

#define f first
#define s second
#define INF 1000000000000000000LL

using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef pair<ll, ii> iii;
typedef vector<iii> viii;

ll find(vi &C, ll x) { return (C[x] == x) ? x : C[x] = find(C, C[x]); }
void merge(vi &C, ll x, ll y) { C[find(C, x)] = find(C, y); }

viii kruskal(viii &edges, ll n) {
    sort(edges.begin(), edges.end());

    vi uf(n);
    for (ll i = 0; i < n; ++i)
        uf[i] = i;

    viii MST;
    for (ll i = 0; i < edges.size(); ++i) {
        ll u = edges[i].second.first;
        ll v = edges[i].second.second;

        if (find(uf, u) != find(uf, v)) {
            merge(uf, u, v);
            MST.push_back(edges[i]);
        }
    }
    return MST;
}

void get_distances(vvi &adj_matrix, ll n) {
    vvi adj_list(n);
    for (ll i = 0; i < n; ++i) {
        for (ll j = 0; j < n; ++j) {
            if (i == j) continue;

            if (adj_matrix[i][j] < INF) {
                adj_list[i].push_back(j);
            }
        }
    }

    for (ll start = 0; start < n; ++start) {
        queue<ll> q;
        q.push(start);
        vi dist(n, INF);
        dist[start] = 0;
        while (!q.empty()) {
            ll cur = q.front(); q.pop();
            for (ll i = 0; i < adj_list[cur].size(); ++i) {
                ll v = adj_list[cur][i];
                if (dist[v] == INF) {
                    dist[v] = dist[cur] + adj_matrix[cur][v];
                    q.push(v);
                }
            }
        }
        adj_matrix[start] = dist;
    }
}

int main() {
    ll n;
    cin >> n;

    viii edges;

    vvi initial_matrix(n, vi(n));
    for (ll i = 0; i < n; ++i) {
        for (ll j = 0; j < n; ++j) {
            cin >> initial_matrix[i][j];
            edges.push_back(iii(initial_matrix[i][j], ii(i, j)));
        }
    }

    viii ans = kruskal(edges, n);
    vvi adj_matrix(n, vi(n, INF));
    for (ll i = 0; i < n; ++i)
        adj_matrix[i][i] = 0;

    for (ll i = 0; i < ans.size(); ++i) {
        adj_matrix[ans[i].s.f][ans[i].s.s] = ans[i].f;
        adj_matrix[ans[i].s.s][ans[i].s.f] = ans[i].f;
    }

    get_distances(adj_matrix, n);
    if (adj_matrix == initial_matrix) {
        cerr << "Input results from a valid weighted tree" << endl;
        return 42;
    }
    else {
        cerr << "Error: input does not result from a valid tree" << endl;
        return 1;
    }
}