#include <bits/stdc++.h>

#define NMAX 50010
#define oo (1 << 30)
#define NO_PARENT (-1)

using namespace std;

class Task {
public:
  void solve() {
    read_input();
    get_result();
  }

private:
  int n, m;
  int source;
  vector<pair<int, int>> adj[NMAX];

  queue<int> q;
  vector<int> d;
  vector<int> p;

  void read_input() {
    fstream fin("bellmanford.in");
    fin >> n >> m;
    d.resize(n + 1);
    p.resize(n + 1);

    source = 1;

    for (int i = 1; i <= m; ++i) {
      int x, y, c;
      fin >> x >> y >> c;

      adj[x].push_back({y, c});
    }
    fin.close();
  }

  void get_result() {
    if (BellmanFord(source, d, p)) {
      cout << "Ciclu negativ!";
    } else {
      print_output();
    }
  }

  bool BellmanFord(int source, vector<int> &d, vector<int> &p) {
    vector<int> used(n + 1, 0);

    for (int i = 1; i <= n; ++i) {
      d[i] = oo;
      p[i] = NO_PARENT;
    }

    p[source] = 0;
    d[source] = 0;
    q.push(source);

    while (!q.empty()) {
      int node = q.front();
      q.pop();

      ++used[node];
      if (used[node] == n) {
        return true;
      }

      for (auto &edge : adj[node]) {
        int neighbour = edge.first;
        int cost_edge = edge.second;

        if (d[node] + cost_edge < d[neighbour]) {

          d[neighbour] = d[node] + cost_edge;
          p[neighbour] = node;
          q.push(neighbour);
        }
      }
    }

    return false;
  }

  void print_output() {
    ofstream fout("bellmanford.out");
    for (int i = 1; i <= n; ++i) {
      if (i == source) {
        continue;
      }
      cout << d[i] << " ";
    }
    cout << "\n";
  }
};

int main() {
  Task *task = new Task();
  task->solve();
  delete task;

  return 0;
}