#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int NMAX = 1e4;

struct edge {
  short int from, to, cost;
};

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  #ifndef ONLINE_JUDGE
  freopen("bellmanford.in", "r", stdin);
  freopen("bellmanford.out", "w", stdout);
  #endif

  int n, m; cin >> n >> m;
  vector<edge> v(m);
  vector<int> dist(n + 1, INF);
  dist[1] = 0;
  for (int i = 0; i < m; i++) {
    cin >> v[i].from >> v[i].to >> v[i].cost;
  }
  bool ok = 1;

  for (int i = 1; i < n && ok; i++) {
    ok = 0;
    for (edge x : v) {
      if (dist[x.from] + x.cost < dist[x.to]) {
        dist[x.to] = dist[x.from] + x.cost;
        ok = 1;
        break;
      }
    }
  }
  ok = 0;
  for (edge x : v) {
    if (dist[x.from] + x.cost < dist[x.to]) {
      dist[x.to] = dist[x.from] + x.cost;
      ok = 1;
      break;
    }
  }

  if (ok) {
    cout << "Ciclu negativ!";
  }
  else {
    for (int i = 2; i <= n; i++) {
      cout << dist[i] << ' ';
    }
  }

  return 0;
}