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

using namespace std;

# define inf 10000000

struct camp
{
       int a, b, c;
       }G[250005];

int i, m, n, ok, cost[50005];

int verif()
{int i;
    for (i = 1; i <= m; i++)
    if (cost[G[i].a] + G[i].c < cost[G[i].b])
       return 1;
    return 0;
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    
    scanf("%d%d",&n,&m);
    
    for (i = 1; i <= m; i++)
    {
        scanf("%d%d%d",&G[i].a,&G[i].b,&G[i].c);
        if (G[i].a == 1) cost[G[i].b] = G[i].c;
        }
        
    for (i = 2; i <= n; i++)
    if (!cost[i]) cost[i] = inf;
    
    while (!ok)
    {
          ok = 1;
          for (i = 1; i <= m; i++)
          if (cost[G[i].b] > cost[G[i].a] + G[i].c)
                           cost[G[i].b] = cost[G[i].a] + G[i].c, ok = 0;
          }         
          
    if (verif())
    {
                printf("Ciclu negativ!");
                return 0;
                }
    
    for (i = 2; i <= n; i++)
    printf("%d ",cost[i]);
    
    
return 0;
}