#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, 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<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);
  vector<int> vis(n);

  int iters = 0;
  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 (auto itr : graph[node]) {
      int vec, cost; tie(vec, cost) = itr;
      push(vec, cost + dist[node], node);
    }
  }

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

  return 0;
}