#include <fstream>
#include <vector>
#include <queue>
#include <bitset>

using namespace std;

const int MAX_N = 50001;
const int INF = 1000000000;

struct arc {
  int extremitate;
  int cost;
};

vector<arc> arce[MAX_N];
vector<arc>::iterator it;
queue<int> Q;
bitset<MAX_N> in_coada;
vector<int> dist(MAX_N, INF);
int ap_in_coada[MAX_N], x, y, c, e, n, m, i;
arc a;
bool ciclu_negativ;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int main() {
  fin >> n >> m;
  for (i = 1; i <= m; i++) {
    fin >> x >> a.extremitate >> a.cost;
    arce[x].push_back(a);
  }
  dist[1] = 0, Q.push(1), in_coada[1] = true;
  while (not Q.empty() and not ciclu_negativ) {
    x = Q.front();
    Q.pop();
    in_coada[x] = false;
    for (it = arce[x].begin(); it != arce[x].end(); it++) { // pentru toate arcele care pleaca din x
      e = it->extremitate, c = it->cost;
      if (dist[x] < INF) // Altfel nu poate aduce o imbunatatire.
        if (dist[e] > dist[x] + c) { // Distanta pana la it->extremitate poate fi imbunatatita.
          dist[e] = dist[x] + c; // Actualizam distanta cu valoarea mai buna.
          if (not in_coada[e])
            if (ap_in_coada[e] >= n)
              ciclu_negativ = true;
            else {
              Q.push(e); // Ar putea aduce imbunatatiri mai tarziu.
              in_coada[e] = true;
              ap_in_coada[e]++;
            }
        }
    }
  }
  if (not ciclu_negativ) {
    for (i = 2; i <= n; i++)
      fout << dist[i] << " ";
  }
  else
    fout << "Ciclu negativ!\n";
  return 0;
}