#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;
    in >> 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;
}