#include<fstream>
#include<queue>
#include<iostream>
#include<vector>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
struct qwerty{
    int val;
    short weight;
};
vector <qwerty>x[50500];
int s=0,S=0;
queue<int>q;
int z[50500],i,j,n,m,a,b;
bool v[50500];
int pr1(){
    while(!q.empty()){
        if(z[a]<S)
            return 1;
        a=q.front();
        q.pop();
        v[a]=false;
        for(i=0;i<x[a].size();i++)
            if(z[x[a][i].val]>z[a]+x[a][i].weight){
                z[x[a][i].val]=z[a]+x[a][i].weight;
                if(v[x[a][i].val]==false){
                    q.push(x[a][i].val);
                    v[x[a][i].val]=true;
                }
            }
    }
    return 2;
}
int main(){
    z[1]=0;
    v[1]=true;
    short c;
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>a>>b>>c;
        x[a].push_back({b,c});
        if(c>0)
            s+=c;
        else
            S+=c;
    }
    for(i=2;i<=n;i++)
        z[i]=s+2;
    q.push(1);
    int aa=pr1();
    if(aa==2)
        for(i=2;i<=n;i++)
            fout<<z[i]<<' ';
    else
        fout<<"Ciclu negativ!";
    return 0;
}