#include <bits/stdc++.h>

using namespace std;

ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

const int INF = (1 << 30);

struct arc{
  int y, c, cnt;
};

vector<arc>v[50002];
int n, m, x, y, c, d[50002];

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;

int main()
{
  fin >> n >> m;
  for (int i = 1; i <= m; i++) {
    fin >> x >> y >> c;
    v[x].push_back({y, c, 0});
  }
  for (int i = 2; i <= n; i++)
    d[i] = INF;
  pq.push({0, 1});
  bool ok = 1;
  while (!pq.empty() && ok) {
    int nod = pq.top().second;
    pq.pop();
    for (auto &it: v[nod]) {
      if (d[nod] + it.c < d[it.y]) {
        it.cnt++;
        if (it.cnt >= n) {
          ok = 0;
          break;
        }
        d[it.y] = d[nod] + it.c;
        pq.push({d[it.y], it.y});
      }
    }
  }
  if (!ok)
    fout << "Ciclu negativ!";
  else
    for (int i = 2; i <= n; i++)
      fout << d[i] << " ";
  return 0;
}