#include<bits/stdc++.h>
#define Nmax 50005
#define inf 51234567

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

vector<pair<int,int>> G[Nmax];
int val[Nmax];

int main(){ //varianta simpla de O(N*M) + mica optimizare
    int n,m,i,j,a,b,cost,ok;
    fin>>n>>m;
    for(i = 1; i <= m; i++){
        fin>>a>>b>>cost;
        G[a].push_back(make_pair(b,cost));
    }
    for(i = 1; i <= n; i++){
        val[i] = inf;
    }
    val[1] = 0;
    for(i = 1; i <= n-1; i++){
        ok = 1;
        for(j = 1; j <= n; j++){
            for(auto vecin: G[j]){
                if(val[vecin.first] > vecin.second + val[j]){
                    val[vecin.first] = vecin.second + val[j];
                    ok = 0;
                }
            }
        }
        if(ok){
            break;
        }
    }
    for(j = 1; j <= n; j++){
        for(auto vecin: G[j]){
            if(val[vecin.first] > vecin.second + val[j]){
                fout<<"Ciclu negativ!";
                return 0;
            }
        }
    }
    for(i = 2; i <= n; i++){
        fout<<val[i]<<' ';
    }
	return 0;
}