#include<stdlib.h>
#include<cstdio>

#define maxn 50005
#define maxm 250005
#define inf 100000005
struct muchie
{
       long a,b,c;
}e[maxm];

long m,n,i,j,cost[maxm];

void init()
{long i;
     cost[1] = 0;
     for (i=2;i<=n;i++)
     cost[i] = inf;
}

void solv()
{long j,i;
     for (i=1;i<=n;i++)
         for (j=1;j<=m;j++)
         if (cost[e[j].a] + e[j].c < cost[e[j].b] )
         cost[e[j].b] = cost[e[j].a] + e[j].c;
}
long negativ()
{long i;
    for (i=1;i<=m;i++)
    if (cost[e[i].a] + e[i].c < cost[e[i].b] )
         return 1;
    return 0;
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%ld%ld",&n,&m);
    
    for (i=1;i<=m;i++)
        scanf("%ld%ld%ld",&e[i].a,&e[i].b,&e[i].c);
    
    init();
    solv();
    
    if (negativ())
    {
       printf("ciclu negative!\n");
       return 0;
       }            
       
       for (i=2;i<=n;i++)
       printf("%ld ",cost[i]);
                   
return 0;
}