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

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

  vector<vector<pair<int, int>>> adj(N + 1);
  vector<int> dist(N + 1, inf);
  vector<int> inQueue(N + 1, 0);
  vector<int> countRelax(N + 1, 0);

  for (int i = 0; i < M; i++) {
    int u, v, w;
    fin >> u >> v >> w;
    adj[u].push_back({v, w});
  }

  queue<int> q;

  dist[1] = 0;
  q.push(1);
  inQueue[1] = 1;

  while (!q.empty()) {
    int u = q.front();
    q.pop();
    inQueue[u] = 0;

    for (auto &[v, w] : adj[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        if (!inQueue[v]) {
          q.push(v);
          inQueue[v] = 1;
          countRelax[v]++;
          if (countRelax[v] >= N) {
            fout << "Ciclu negativ!";
            return 0;
          }
        }
      }
    }
  }
  for (int i = 2; i <= N; i++)
    fout << dist[i] << " ";
  return 0;
}