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

using namespace std;

struct camp
{
       long a, b;
       }e[250005];
long cost[50005], c[250005], m, n;

int verif()
{long i;
     for (i = 1; i <= m; i++)
        if (cost[e[i].a] + c[i] < cost[e[i].b])
           return 1;
        return 0;
     }
int main()
{long i, j;
    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, &c[i]);
        
    cost[1] = 0;
    for (i = 2; i <= n; i++)
    cost[i] = 1000000000;
   
    
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        if (cost[e[j].a] + c[j] < cost[e[j].b]) 
                         cost[e[j].b] = cost[e[j].a] + c[j];
    
    if (verif()) 
    {
                 printf("Ciclu negativ");
                 return 0;
                 }
    
    for (i = 2; i <= n; i++)
    printf("%ld ",cost[i]);
    
return 0;
}