#include <iostream>
#include <cstdio>

using namespace std;

const int NMAX = 50000;
const int MMAX = 250000;
const int INF = 1000000000;

struct muchie {
  int a, b, cost;

  muchie(int ta = 0, int tb = 0, int tcost = 0) : a(ta), b(tb), cost(tcost) {}
};

int n, m;
int d[NMAX + 5];
muchie muchii[MMAX + 5];

bool bellman_ford(int start) {
  for(int i = 1; i <= n; i++)
    d[i] = INF;
  d[start] = 0;

  for(int i = 1; i < n; i++)
    for(int j = 1; j <= m; j++) {
      int a = muchii[j].a, b = muchii[j].b, cost = muchii[j].cost;
      if(d[a] + cost < d[b])
        d[b] = d[a] + cost;
    }

  for(int j = 1; j <= m; j++) {
    int a = muchii[j].a, b = muchii[j].b, cost = muchii[j].cost;
    if(d[a] + cost < d[b])
      return false;
  }

  return true;
}

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, z;

    scanf("%d %d %d", &x, &y, &z);
    muchii[i] = muchie(x, y, z);
  }

  if(!bellman_ford(1))
    printf("Ciclu negativ!");
  else
    for(int i = 2; i <= n; i++)
      printf("%d ", d[i]);

  return 0;
}