// Paste me into the FileEdit configuration dialog

#include <cmath>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;

class SafeReturn {
public:


    #define trav(it, v) for(typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)
    #define rep(i, a, b) for(int i = (a); i < int(b); ++i)

    vector<int> match;
    vector<bool> seen;
    template<class G>
    bool find(int j, G &g) {
        if (match[j] == -1) return true;
        seen[j] = true; int di = match[j];
        trav(e, g[di])
        if (!seen[*e] && find(*e, g)) {
            match[*e] = di;
            match[j] = -1;
            return true;
        }
        return false;
    }
    template<class G>
    int dfs_matching(G &g, int n, int m) {
        match.assign(m, -1);
        rep(i,0,n) {
            seen.assign(m, false);
            trav(j,g[i])
            if (find(*j, g)) {
                match[*j] = i;
                break;
            }
        }
        return m - count(match.begin(), match.end(), -1);
    }

    int minRisk( int N, vector <string> streets ) {
        int T = streets.size();
        int dist[T][T];
        for(int i = 0; i<T; ++i)
            for(int j = 0; j<T; ++j)
                dist[i][j] = 1000000;
        for(int i = 0; i<T; ++i){
            for(int j = 0; j<T; ++j){
                if(streets[i][j] != '-'){
                    dist[i][j] = streets[i][j]-'0';
                }
            }
        }
        for(int k = 0; k<T; ++k)
            for(int i = 0; i<T; ++i)
                for(int j = 0; j<T; ++j){
                    dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
                }
                vector<vector<int> > leftPartition(N);
            for(int i = 1; i<=N; ++i)
                for(int j = 1; j<=N; ++j){
                    if(i != j && dist[0][i]+dist[i][j] == dist[0][j]){

                        //j kan följa i utan konsekvenser!
                        leftPartition[j-1].push_back(i-1);
                    }
                }
                return N-dfs_matching(leftPartition, N, N);
    }
};