#include <cstdio>
#define MAXN 50000
#define MAXM 250000
#define INF 1000000000
int v[MAXM+1],ind[MAXN+1],next[MAXM+1],dist[MAXN+1],cod[MAXN],cost[MAXM+1],nr[MAXN+1];
char vf[MAXN+1];
int main(){
    FILE*fi,*fout;
    int x,y,c,n,m,i;
    fi=fopen("bellmanford.in" ,"r");
    fout=fopen("bellmanford.out" ,"w");
    fscanf(fi,"%d%d" ,&n,&m);
    for(i=1;i<=m;i++){
        fscanf(fi,"%d%d%d" ,&x,&y,&c);
        v[i]=y;
        cost[i]=c;
        next[i]=ind[x];
        ind[x]=i;
    }
    for(i=2;i<=n;i++)
        dist[i]=INF;
    int begin=0,end=1;
    cod[0]=1;
    nr[1]=vf[1]=1;
    while(begin<end&&nr[cod[begin]]<n){
        int poz;
        x=cod[begin%MAXN];
        vf[x]=0;
        begin++;
        poz=ind[x];
        while(poz){
            if(vf[v[poz]]==0){
                if(dist[v[poz]]>dist[x]+cost[poz]){
                    dist[v[poz]]=dist[x]+cost[poz];
                    cod[end%MAXN]=v[poz];
                    vf[v[poz]]=1;
                    nr[v[poz]]++;
                    end++;
                }
            }
            poz=next[poz];
        }
    }
    if(begin<end)
        fprintf(fout,"Ciclu negativ!");
    else
        for(i=2;i<=n;i++){
            if(dist[i]==INF)
               dist[i]=0;
           fprintf(fout,"%d " ,dist[i]);
        }
    fclose(fi);
    fclose(fout);
    return 0;
}