#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) {
  bool modif[NMAX + 5];
  queue<int> q;

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

  q.push(start);

  for(int i = 1; i < n; i++) {
    for(int j = 1; j <= n; j++)
      if(modif[j])
        q.push(j);

    while(!q.empty()) {
      int crt = q.front();
      q.pop();

      for(muchie vec: v[crt])
        if(d[crt] + vec.cost < d[vec.nod]) {
          d[vec.nod] = d[crt] + vec.cost;
          q.push(vec.nod);
          modif[vec.nod] = true;
        }
    }
  }

  for(int i = 1; i <= n; i++)
    for(muchie vec: v[i])
      if(d[i] + vec.cost < d[vec.nod])
        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);
    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;
}