#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

int const nmax = 50000;

struct Edge {
    int to;
    int cost;
};

int n, m;
vector<Edge> g[1 + nmax];
bool vis[1 + nmax];
int count[1 + nmax];
int sol[1 + nmax];

bool bfs() {
  queue<int> q;
  q.push(1);
  while (!q.empty()) {
    int from = q.front();
    if (count[from] <= n) {
      vis[from] = 0;
      q.pop();
      for (int i = 0; i < g[from].size(); i++) {
        Edge &e = g[from][i];
        if (sol[e.to] == 0 || sol[from] + e.cost < sol[e.to]) {
          sol[e.to] = sol[from] + e.cost;
          if (vis[e.to] == 0) {
            q.push(e.to);
            vis[e.to] = 1;
            count[e.to]++;
          }
        }
      }
    } else
      return 0;
  }
  return 1;
}

int main() {
  in >> n >> m;
  for (int i = 1; i <= m; i++) {
    int from, to, cost;
    in >> from >> to >> cost;
    g[from].push_back({to, cost});
  }

  if (bfs() == 1) {
    for (int i = 2; i <= n; i++)
      out << sol[i] << " ";
  } else
    out << "Ciclu negativ!";
  return 0;
}