#include <stdio.h>
#include <queue>
#include <algorithm>

#define N 50005
#define M 250005
#define INF 50000005
using namespace std;


struct Nod {
    int v;
    int cost;
    Nod* next;
};
Nod* lv[N];
int n,m;
int d[N];
int isIn[N];
queue<int> Q;
void Insert(Nod *&c, int val, int cos) {
    Nod* nou = new Nod();
    nou -> v = val;
    nou -> cost = cos;
    nou -> next = c;
    c = nou;
}
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);
        Insert(lv[x], y, cost);
    }
    for(int i = 2; i <= n; i++) {
     d[i] = INF;
     isIn[i] = 0;
    }
    isIn[1] = 1;
    Q.push(1);
    int steps = 0;
    while (Q.size() != 0 && steps <= m) {
     steps++;
     isIn[Q.front()] = 0;
     int aux = Q.front();
     Q.pop();
     for(Nod* it = lv[aux]; it != 0; it = it -> next)
      if (d[it -> v] > d[aux] + it -> cost) {
       d[it -> v] = d[aux] + it -> cost;
       if (isIn[it->v] == 0) {
           Q.push(it->v);
           isIn[it->v] = 1;
       }
      }
    }
     int j = 0;
    for(int i = 1; i <= n; i++)
     for(Nod* it = lv[i]; it != 0; it = it -> next) {
       if (d[it -> v] > d[i] + it -> cost)
        j = 1;
    }
    if (j == 1) printf("Ciclu negativ!\n");
    else {
      for(int i = 2; i <= n; i++)
        printf("%d ",d[i]);
    }

    return 0;
}