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


struct Edge { int a, b, c; };

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

  int n, m; cin >> n >> m;
  vector<Edge> es(m);
  for (int i = 0; i < m; ++i) {
    auto& e = es[i];
    cin >> e.a >> e.b >> e.c; --e.a; --e.b;
  }

  mt19937 rng(time(0));
  vector<int> o(n);
  iota(o.begin(), o.end(), 0);
  shuffle(o.begin(), o.end(), rng);
  sort(es.begin(), es.end(),
    [&](const Edge& e1, const Edge& e2) {
      return make_tuple(o[e1.a] < o[e1.b], o[e1.a], o[e1.b], e1.c) <
        make_tuple(o[e2.a] < o[e2.b], o[e2.a], o[e2.b], e2.c);
    });

  vector<int> dist(n, 1e9), prev(n, -1);
  auto relax = [&](const Edge& e) {
    if (dist[e.b] <= dist[e.a] + e.c)
      return false;

    dist[e.b] = dist[e.a] + e.c;
    prev[e.b] = e.a;
    return 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;
  };

  dist[0] = 0;
  int ch = 1;
  while (ch--) {
    for (const auto& e : es)
      ch |= relax(e);
    if (has_cycle()) {
      cout << "Ciclu negativ!" << endl;
      return 0;
    }
  }

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

  return 0;
}