#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[it->extremitate] > dist[x] + it->cost) { // 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;
}

/*
b->c
     u  v  x  y  z
     6 oo  7 oo  0
u,v: 6 11  7 oo  0
u,y: 6 11  7  2  0
x,v: 6  4  7  2  0
------------------
c->d
     u  v  x  y  z
     6  4  7  2  0
v,u: 2  4  7  2  0
------------------
d->e
     u  v  x  y  z
     2  4  7  2  0
u,y: 2  4  7 -2  0
*/