#include <bits/stdc++.h>

using namespace std;

class InParser {
private:
  FILE* fin;
  char* buff;
  int sp;

  char read_ch() {
    ++sp;
    if (sp == 4096) {
      sp = 0;
      fread(buff, 1, 4096, fin);
    }
    return buff[sp];
  }

public:
  InParser(const char* nume) {
    fin = fopen(nume, "r");
    buff = new char[4096]();
    sp = 4095;
  }

  InParser& operator >> (int& n) {
    char c;
    while (!isdigit(c = read_ch()) && c != '-');
    int sgn = 1;
    if (c == '-') {
      n = 0;
      sgn = -1;
    } else {
      n = c - '0';
    }
    while (isdigit(c = read_ch())) {
      n = 10 * n + c - '0';
    }
    n *= sgn;
    return *this;
  }
};

bool DFS(int node, const vector<int>& nxt, vector<int>& vis) {
  int vec = nxt[node];
  vis[node] = 1;
  if (vec != -1) {
    if (vis[vec] == 1) return true;
    if (vis[vec] == 0 && DFS(vec, nxt, vis))
      return true;
  }
  vis[node] = 2;
  return false;
}

int main() {
  InParser cin("bellmanford.in");
  ofstream cout("bellmanford.out");

  int n, m; cin >> n >> m;
  vector<tuple<int, int, int>> es(m);
  for (int i = 0; i < m; ++i) {
    int a, b, c; cin >> a >> b >> c; --a; --b;
    es[i] = make_tuple(a, b, c);
  }
  sort(es.begin(), es.end());

  vector<int> dist(n, 1e9), prev(n, -1),
    q(n, -1), inq(n, false);
  int b = 0, e = 0;
  auto push = [&](int node, int d, int p) {
    if (dist[node] <= d) return;
    dist[node] = d;
    prev[node] = p;
    if (!inq[node]) {
      q[e] = node;
      if (++e == n)
        e = 0;
    }
    inq[node] = true;
  };

  push(0, 0, -1);
  vector<int> vis(n);

  vector<int> start(n + 1, m);
  for (int i = m - 1; i >= 0; --i)
    start[get<0>(es[i])] = i;

  while (b != e) {
    int node = q[b];
    if (++b == n) b = 0;
    inq[node] = false;

    if (b == 0) {
      fill(vis.begin(), vis.end(), 0);
      for (int i = 0; i < n; ++i) {
        if (!vis[i] && DFS(i, prev, vis)) {
          cout << "Ciclu negativ!" << endl;
          return 0;
        }
      }
    }

    for (int i = start[node]; i < start[node + 1]; ++i) {
      int vec, cost; tie(ignore, vec, cost) = es[i];
      push(vec, cost + dist[node], node);
    }
  }

  for (int i = 1; i < n; ++i)
    cout << dist[i] << " ";
  cout << endl;

  return 0;
}