B-A'2

#include <bits/stdc++.h>
using namespace std;
#define all(a) a.begin(), a.end()
#define forn(i, a, b, delta) for (ll i = a; i < b; i += delta)
#define FAST ios_base::sync_with_stdio(false); cin.tie(nullptr)
using ll = long long;
const ll INFIN = 1'000'000'000LL * 3'000LL;
ll n;

vector<ll> path(ll u, ll v, const vector< vector<ll> >& p) {
    if (p[u][v] == -1) return {};
    vector<ll> left, right;
    ll mid = p[u][v];
    left = path(u, mid, p);
    right = path(mid, v, p);
    left.push_back(mid);
    for (auto& e : right) {
        left.push_back(e);
    }
    return left;
}

ll test(vector< vector<ll> > weight_copy, vector< vector<ll> > weight, pair<ll, ll> delet) {
    ll ans = 0;
    vector< vector<ll> > weight2(n, vector<ll>(n));
    forn(i, 0, n, 1) {
        forn(j, 0, n, 1) {
            weight2[i][j] = (weight_copy[i][j] <= 0 ? INFIN : weight_copy[i][j]);
        }
    }
    weight2[delet.first][delet.second] = INFIN;
    weight2[delet.second][delet.first] = INFIN;
    forn(i, 0, n, 1) {
        forn(u, 0, n, 1) {
            forn(v, 0, n, 1) {
                ll mb = weight2[u][i] + weight2[i][v];
                if (mb < weight2[u][v] and weight2[u][i] < INFIN and weight2[i][v] < INFIN) {
                    //update:
                    weight2[u][v] = mb;
                }
            }
        }
    }

    ans = 0;
    forn(v, 1, n, 1) {
        if (weight[0][v] != weight2[0][v]) ans += 1;
    }
    return ans;
}

int main() {
    FAST;
     cin >> n;
    vector< vector<ll> > weight(n, vector<ll>(n)), p(n, vector<ll>(n, -1));
    forn(i, 0, n, 1) {
        forn(j, 0, n, 1) {
            ll w; cin >> w;
            weight[i][j] = (w <= 0 ? INFIN : w);
        }
    }
    auto weight_copy = weight;
    forn(i, 0, n, 1) {
        forn(u, 0, n, 1) {
            forn(v, 0, n, 1) {
                ll mb = weight[u][i] + weight[i][v];
                if (mb < weight[u][v] and weight[u][i] < INFIN and weight[i][v] < INFIN) {
                    //update:
                    weight[u][v] = mb;
                    p[u][v] = i;
                }
            }
        }
    }

    map<pair<ll, ll>, ll> uses;
    forn(i, 1, n, 1) {
        if (weight[0][i] == INFIN) continue;
        vector<ll> travel;
        travel.push_back(0);
        for (auto&& e : path(0, i, p)) travel.push_back(e);
        travel.push_back(i);
        forn(j, 1, travel.size(), 1) {
            uses[{travel[j - 1], travel[j]}] += 1;
        }
    }

    ll ans = 0;
    pair<ll, ll> delet;
    //cerr << "map of uses:\n";
    for (auto [a, b] : uses) {
        if (ans < b) {
            ans = max(ans, test(weight_copy, weight, a));
            delet = a;
        }
        //cerr << "{ " << a.first << ", " << a.second << " } " << " : " << b << endl;
    }
    //cout << ans << endl;

    cout << ans << endl;
}