#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

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

struct muchie {
  int nod, cost;

  muchie(int tnod = 0, int tcost = 0) : nod(tnod), cost(tcost) {}
};

int n, m;
int d[NMAX + 5];
vector<muchie> v[NMAX + 5];

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

  queue<int> q;
  q.push(start);
  q.push(-1);

  int crt;
  for(int i = 1; i < n; i++) {
    crt = q.front();
    q.pop();

    while(crt != -1) {
      for(muchie vec: v[crt])
        if(d[crt] + vec.cost < d[vec.nod]) {
          d[vec.nod] = d[crt] + vec.cost;
          q.push(vec.nod);
        }

      crt = q.front();
      q.pop();
    }

    q.push(-1);
  }

  crt = q.front();
  q.pop();

  while(crt != -1) {
    for(muchie vec: v[crt])
      if(d[crt] + vec.cost < d[vec.nod])
        return false;

    crt = q.front();
    q.pop();
  }

  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);
    v[x].push_back(muchie(y, z));
  }

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

  return 0;
}