#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, 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
      //if (dist[x] < INF) // Altfel nu poate aduce o imbunatatire.
      if (dist[x]+it->cost < dist[it->extremitate]) { // Distanta pana la it->extremitate poate fi imbunatatita.
        dist[it->extremitate] = dist[x] + it->cost; // Actualizam distanta cu valoarea mai buna.
        if (not in_coada[it->extremitate])
          if (ap_in_coada[it->extremitate] >= n)
            ciclu_negativ = true;
          else {
            Q.push(it->extremitate); // Ar putea aduce imbunatatiri mai tarziu.
            in_coada[it->extremitate] = true;
            ap_in_coada[it->extremitate]++;
          }
      }
  }
  if (not ciclu_negativ) {
    for (i = 2; i <= n; i++)
      fout << dist[i] << " ";
  }
  else
    fout << "Ciclu negativ!\n";
  return 0;
}