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

using namespace std;

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

struct arc {
  int extremitate;
  int cost;
};

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

int main() {
  fin >> n >> m;
  for (int i = 0; i < m; i++) {
    fin >> x >> a.extremitate >> a.cost;
    muchii[x].push_back(a);
  }
  dist[1] = 0, Q.push(1), in_coada[1] = true;
  while (!Q.empty() and !ciclu_negativ) {
    x = Q.front();
    Q.pop();
    in_coada[x] = false;
    for (it = muchii[x].begin(); it != muchii[x].end(); it++)
      if (dist[x] < INF)
        if (dist[it->extremitate] > dist[x] + it->cost) { // distanta pana la it->extremitate poate fi imbunatatita
          dist[it->extremitate] = dist[x] + it->cost;
          if (!in_coada[it->extremitate])
            if (ap_in_coada[it->extremitate] > n)
              ciclu_negativ = true;
            else {
              Q.push(it->extremitate);
              in_coada[it->extremitate] = true;
              ap_in_coada[it->extremitate]++;
            }
        }
  }
  if (!ciclu_negativ) {
    for (int i = 2; i <= n; ++ i)
      fout << dist[i] << " ";
  }
  else
    fout << "Ciclu negativ!\n";
  return 0;
}