#include <bits/stdc++.h>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
const int inf = 1e9 + 7;

struct Edge {
  int u, v, w;
};

int main() {
  int N, M;
  fin >> N >> M;

  vector<Edge> edges(M);

  for (int i = 0; i < M; i++)
    fin >> edges[i].u >> edges[i].v >> edges[i].w;

  vector<int> dist(N + 1, inf);

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

  for (int i = 1; i <= N - 1; i++) {
    for (auto e : edges) {
      if (dist[e.u] != inf && dist[e.u] + e.w < dist[e.v])
        dist[e.v] = dist[e.u] + e.w;
    }
  }

  bool hasCycle = 0;
  for (auto e : edges) {
    if (dist[e.u] != inf && dist[e.u] + e.w < dist[e.v]) {
      hasCycle = 1;
      break;
    }
  }

  if (hasCycle)
    fout << "Ciclu negativ!";
  else {
    for (int i = 2; i <= N; i++)
      fout << dist[i] << " ";
  }

  return 0;
}