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

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

  int n, m; cin >> n >> m;
  vector<vector<pair<int, int>>> graph(n);
  for (int i = 0; i < m; ++i) {
    int a, b, c; cin >> a >> b >> c; --a; --b;
    graph[a].emplace_back(b, c);
  }

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

  vector<int> deg(n), qc; qc.reserve(n);
  auto has_cycle = [&]() {
    fill(deg.begin(), deg.end(), 0);
    for (int i = 0; i < n; ++i) {
      if (prev[i] != -1)
        deg[prev[i]] += 1;
    }
    qc.clear();
    for (int i = 0; i < n; ++i)
      if (deg[i] == 0) 
        qc.push_back(i);
    for (int i = 0; i < (int)qc.size(); ++i) {
      int node = qc[i];
      if (prev[node] != -1 && --deg[prev[node]] == 0)
        qc.push_back(prev[node]);
    }
    return (int)qc.size() < n;
  };

  push(0, 0, -1);
  
  int iters = 0;
  while (b != e) {
    int node = q[b];
    if (++b == n) b = 0;
    inq[node] = false;
    
    for (auto itr : graph[node]) {
      int vec, cost; tie(vec, cost) = itr;
      push(vec, cost + dist[node], node);
      if ((++iters) % n == 0 && has_cycle()) {
        cout << "Ciclu negativ!" << endl;
        return 0;
      }
    }
  }

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

  return 0;
}