#include <algorithm>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <set>
#include <string.h>
#include <vector>

using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

int main() {
  // auto &in = cin;
  // auto &out = cout;
  int N, M;
  in >> N >> M;
  vector<vector<pair<int, int>>> edges(N + 1);
  for (int i = 1; i <= M; i++) {
    int from, to, cost;
    cin >> from >> to >> cost;

    edges[from].emplace_back(to, cost);
  }

  vector<int> distance(N + 1, ~(1 << 31));
  distance[1] = 0;
  for (int i = 1; i <= N - 1; i++) {
	  for (int node = 1; node <= N; node++)
		  for (const auto &edge : edges[node]) {
			  if (distance[edge.first] > distance[node] + edge.second)
				  distance[edge.first] = distance[node] + edge.second;
		  }
  }

  bool negativeCycle = false;
  for (int node = 1; node <= N && !negativeCycle; node++)
	  for (const auto &edge : edges[node]) {
		  if (distance[edge.first] > distance[node] + edge.second)
			  negativeCycle = true;
	  }

  if (negativeCycle) {
	  out << "Ciclu negativ!";
	  return 0;
  }

  for (int i = 2; i <= N; i++)
    out << distance[i] << ' ';

  return 0;
}