#include <iostream>
#include <fstream>
#include <vector>
#include <limits>

using namespace std;

class Edge {
  public:
    Edge(int uu, int vv, int w): u(uu), v(vv), weight(w) {}
    int u, v, weight;
};

vector<Edge> edges;
int n, m;

int main() {
  ifstream fin;
  fin.open("bellmanford.in");

  fin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v, weight;
    fin >> u >> v >> weight;
    edges.push_back(Edge(u, v, weight));
  }
  fin.close();

  vector<int> dist(n + 1, numeric_limits<int>::max() / 3);

  int src = 1;
  dist[src] = 0;

  for (int i = 0; i < n; i++) {
    for (auto& edge : edges) {
      if (dist[edge.u] + edge.weight < dist[edge.v]) {
        dist[edge.v] = dist[edge.u] + edge.weight;
      }
    }
  }

  ofstream fout;
  fout.open("bellmanford.out");

  for (auto& edge : edges) {
    if (dist[edge.u] + edge.weight < dist[edge.v]) {
      fout << "Ciclu Negativ!" << endl;
      return 0;
    }
  }

  for (int i = 2; i < dist.size(); i++) {
    if (i != 2) {
      fout << " ";
    }
    fout << dist[i];
  }

  fout.close();

  return 0;
}