#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];

queue<int> q;
bool in_queue[NMAX + 5];
int cnt_queue[NMAX + 5];

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

  q.push(start);
  in_queue[start] = true;

  while(!q.empty()) {
    int crt = q.front();
    q.pop();
    in_queue[crt] = false;

    for(muchie vec: v[crt])
      if(d[crt] + vec.cost < d[vec.nod]) {
        d[vec.nod] = d[crt] + vec.cost;
        if(!in_queue[vec.nod]) {
          cnt_queue[vec.nod]++;
          if(cnt_queue[vec.nod] == n)
            return false;

          q.push(vec.nod);
          in_queue[vec.nod] = true;
        }
      }
  }

  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;
}