#include<fstream>
#include<vector>
#include<deque>
using namespace std;
int n, m, i, ok, a, b, C, nod, vecin, cost;
int d[50005], f[50005], viz[50005];
vector< pair<int, int> > v[50005];
deque<int> c;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int main(){
    fin>> n >> m;
    for(i = 1; i <= m; i++){
        fin>> a >> b >> C;
        v[a].push_back( make_pair(b, C));
    }
    for(i = 2; i <= n; i++){
        d[i] = 1000000000;
    }
    c.push_back(1);
    viz[1] = f[1] = 1;
    while( !c.empty()){
        nod = c[0];
        ok = 0;
        for(i = 0; i < v[nod].size(); i++){
            vecin = v[nod][i].first;
            cost = v[nod][i].second;
            if(d[vecin] > d[nod] + cost){
                d[vecin] = d[nod] + cost;
                if(viz[vecin] == 0){
                    viz[vecin] = 1;
                    c.push_back(vecin);
                    f[vecin]++;
                    if(f[vecin] == n){
                        fout<<"Ciclu negativ!\n";
                        return 0;
                    }
                }
            }
        }
        viz[nod] = 0;
        c.pop_front();
    }
    for(i = 2; i <= n; i++){
        fout<< d[i] <<" ";
    }
    return 0;
}