форд 1

#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);
        }
    }
}


void Frd(vector <ed> G, int n, int str){
    int m = G.size();
    vector <int> d(n, inf);
    vector <int> pred(n); //может надо как-то для начала его заполнить?
    d[str] = 0;
    int upd_lst;
    for (int i = 0; i < n; ++i){
        upd_lst = -1;
        for (int j = 0; j < m; ++j){
            if (d[ G[j].fr ] == inf){
                continue;
            }
            if (d[ G[j].to ] > d[ G[j].fr ] + G[j].w){
                d[ G[j].to ] = d[ G[j].fr ] + G[j].w;
                upd_lst = G[j].to;
                pred[ G[j].to ] = G[j].fr;
            }
        }
    }
    if (upd_lst == -1) return;

    int v = upd_lst;
    for (int i = 0; i < n; ++i){
        v = pred[v];
    }
    str = v;
    v = pred[v];
    vector <int> ans = {str};
    while (v != str){
        ans.push_back(v);
        v = pred[v];
    }
    ans.push_back(str);
    reverse(ans.begin(), ans.end());
    for (int i: ans) cout<<i+1<<' ';
    exit(0);
}


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";
        }
	}*/
	vector <int> comp_size(cnt+1,0);
	for (int i = 0; i < n;++i){
        comp_size[ to_comp[i] ]++;
	}
	for (int i = 0; i < cnt + 1; ++i){
        int str = comp[i][0].fr;
        Frd(comp[i], comp_size[i], str);
	}
}
/*
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
*/