#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; // noduri
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 (i = 1; 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[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;
}