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

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;
  bool ok = true;
  vector<vector<pair<int, int>>> v(n + 1);
  vector<int> dist(n + 1, INF), cnt(n + 1);
  vector<bool> inq(n + 1);
  queue<int> q;
  for (int i = 0; i < m; i++) {
    int a, b, c; cin >> a >> b >> c;
    v[a].push_back({b, c});
  }
  dist[1] = 0;
  q.push(1);
  while (q.size() && ok) {
    int a = q.front();
    q.pop();
    inq[a] = 0;
    cnt[a]++;
    if (cnt[a] >= n) {
      ok = 0;
      break;
    }
    for (auto i : v[a]) {
      if (dist[a] + i.second < dist[i.first]) {
        dist[i.first] = dist[a] + i.second;
        if (!inq[i.first]) {
          q.push(i.first);
          inq[i.first] = 1;
        }
      }
    }
  }

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

  return 0;
}