форд белман

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <stack>
#include <set>
#include <map>
#define pii pair <int,int>
#define vec vector
using namespace std;
using ll = long long;
using ld = long double;
using db = double;
void cv(vector <int> &v){
    for (auto x: v) cout<<x<<' ';
    cout<<"\n";
}

void cvl(vector <ll> &v){
    for (auto x: v) cout<<x<<' ';
    cout<<"\n";
}


void cvv(vector <vector <int> > &v){
    for (auto x: v) cv(x);
    cout<<"\n";
}

void cvb(vector <bool> v){
    for (bool x: v) cout<<x<<' ';
    cout<<"\n";
}

void cvs(vector <string>  v){
    for (auto a: v){
        cout<<a<<"\n";
    }
}




struct ed{
    int fr, to, w;
};

int inf = 2e9;

vector <int> to_comp;
vector <int> clr;
vector <vector <int> > Gra;//список смеж

void dfs(int v, int pr, int comp_v){
    clr[v] = 1;
    to_comp[v] = comp_v;
    for (int u: Gra[v]){
        if (u == pr) continue;
        if (clr[u] == 0){
            dfs(u, v, comp_v);
        }
    }
}


int main()
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n; cin>>n;
	int m = 0;
	vector <int> d(n, inf);
	d[0]=0;
	vector <ed> G;//список ребер
	Gra.resize(n);
	vector <int> pred(n);
	for (int i = 0; i < n ;++i){
        for (int j = 0; j < n;++j){
            int ds; cin>>ds;
            if (ds == 100000) continue;
            ed x = {i, j, ds};
            Gra[x.fr].push_back(x.to);
            m++;
            G.push_back(x);
        }
	}
	for (ed x: G){
	   // cout<<x.fr<<' '<<x.to<<' '<<x.w<<"\n";
	}
	to_comp.assign(n, -1);
	clr.assign(n, 0);
	int cnt = -1;
	for (int i = 0; i < n; ++i){
        if (to_comp[i] == -1){
            cnt++;
            dfs(i, i, cnt);
        }
	}
	//cout<<"to_comp\n";
	for (int i = 0; i < n;++i){
        //cout<<i<<' '<<to_comp[i]<<"\n";
	}
	//cout<<"cnt= "<<cnt;
	vector <vector <ed> > comp(cnt+1);
	for (int i = 0; i < m; ++i){
        comp[ to_comp[ G[i].fr ] ].push_back( G[i] );
	}
	/*cout<<"comp\n";
	for (int i = 0; i < cnt+1;++i){
        cout<<i<<"\n";
        for(auto x: comp[i]){
            cout<<x.fr<<' '<<x.to<<' '<<x.w<<"\n";
        }
	}*/
}
/*
13
100000 1 100000 100 100000 100000 100000 100000 100000 100000 100000 100000 100000
100000 100000 10 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000
100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000
100000 -10 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000
100000 100000 100000 100000 100000 1 100000 100000 100000 100000 100000 100000 100000
100000 100000 100000 100000 100000 100000 2 100000 -10 100000 100000 100000 100000
100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000
100000 100000 100000 100000 100000 100000 3 100000 4 100000 100000 100000 100000
100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000
100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 1 100000 3
100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 2 100000
100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 -7
100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 4 0 100000
*/