#include <stdio.h>
#define N 50005
#define M 250005
#define INF 50000005
using namespace std;


struct Muchie {
    int x;
    int y;
    int cost;
};
Muchie lm[M];
int n,m;
int d[N];

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);

    scanf("%d %d",&n,&m);
    for(int i = 1; i <= m; i++) {
        int x, y, cost;
        scanf("%d %d %d",&x,&y,&cost);
        lm[i].x = x;
        lm[i].y = y;
        lm[i].cost = cost;
    }
    for(int i = 2; i <= n; i++)
     d[i] = INF;
    for(int i = 1; i <= (n - 1) / 3; i++)
     for(int j = 1; j <= m; j++)
      if (d[lm[j].y] > d[lm[j].x] + lm[j].cost)
       d[lm[j].y] = d[lm[j].x] + lm[j].cost;
     int j;
     for(j = 1; j <= m; j++)
      if (d[lm[j].y] > d[lm[j].x] + lm[j].cost) {
       printf("Ciclu negativ!\n");
       break;
      }
     if (j == m + 1) {
         for(int i = 2; i <= n; i++)
          printf("%d ",d[i]);
     }

    return 0;
}