#include<bits/stdc++.h>

using namespace std;

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

vector<pair<int,int>> G[50005];
queue<int> Q;
int val[50005], select[50005], update[50005];

int main(){ //varianta optimizata
    int n,m,i,j,a,b,cost,top,nod;
    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] = 51234567;
    }
    val[1] = 0;
    Q.push(1);
    select[1] = 1;
    while(!Q.empty()){
        top = Q.front();
        Q.pop();
        select[top] = 0;
        for(auto vecin: G[top]){
            nod = vecin.first;
            if(val[nod] > val[top] + vecin.second){
                val[nod] = val[top] + vecin.second;
                update[nod]++;
                if(!select[nod]){
                    Q.push(nod);
                    select[nod] = 1;
                }
            }
            if(update[nod] == n){
                fout<<"Ciclu negativ!";
                return 0;
            }
        }
    }
    for(i = 2; i <= n; i++){
        fout<<val[i]<<' ';
    }
	return 0;
}