#include <algorithm>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#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;
    in >> from >> to >> cost;

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

  set<int> inQueue = {1};
  queue<int> que;
  que.push(1);
  const int &inf = ~(1 << 31);
  vector<int> distance(N + 1, inf);
  vector<int> count(N + 1);
  distance[1] = 0;
  count[1] = 1;
  bool negativeCycle = false;
  while (!que.empty() && !negativeCycle) {
    int node = que.front();
    que.pop();
    inQueue.erase(node);

	for (const auto &edge : edges[node]) {
		if (distance[node] != inf &&
			distance[edge.first] > distance[node] + edge.second) {
			distance[edge.first] = distance[node] + edge.second;
			if (inQueue.find(node) == inQueue.end()) {
				if (count[edge.first] > N) {
					negativeCycle = true;
				}
				else {
					inQueue.insert(edge.first);
					que.push(edge.first);
					count[edge.first]++;
				}
			}
		}
	}
  }

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

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

  return 0;
}