#include <stdio.h>
#define INF 2000000000
#define MASK 65535
#define MAXN 50000
#define MAXM 250000
int cost[MAXM+1], val[MAXM+1], next[MAXM+1], dist[MAXN+1], q[MASK+1], lista[MAXN+1], viz[MAXN+1];
char aci[MAXN+1];
int main(){
    int n, m, x, i, st, dr, p, f;
    FILE *fin, *fout;
    fin=fopen("bellmanford.in", "r");
    fout=fopen("bellmanford.out", "w");
    fscanf(fin, "%d%d", &n, &m);
    for(i=1; i<=m; i++){
        fscanf(fin, "%d%d%d", &x, &val[i], &cost[i]);
        next[i]=lista[x];
        lista[x]=i;
    }
    for(i=1; i<=n; i++){
        dist[i]=INF;
    }
    st=0;
    q[0]=1;
    viz[1]=1;
    aci[1]=1;
    dist[1]=0;
    dr=1;
    f=1;
    while((f)&&(st<dr)){
        x=q[st&MASK];
        st++;
        p=lista[x];
        while(p){
            if(dist[x]+cost[p]<dist[val[p]]){
                dist[val[p]]=dist[x]+cost[p];
                viz[val[p]]++;
                if(viz[val[p]]==n){
                    f=0;
                }
                if(aci[val[p]]==0){
                    aci[val[p]]=1;
                    q[dr&MASK]=val[p];
                    dr++;
                }
            }
            p=next[p];
        }
        aci[x]=0;
    }
    if(f==0){
        fprintf(fout, "Ciclu negativ!\n");
    }else{
        for(i=2; i<n; i++){
            fprintf(fout, "%d ", dist[i]);
        }
        fprintf(fout, "%d\n", dist[n]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}