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

std::ifstream fin ("bellmanford.in");
std::ofstream fout ("bellmanford.out");

const int MAX_N = 50000;
const int INF = (1 << 30);
struct Muchie {
  int vecin;
  int cost;
};

int n, m;
std::vector<Muchie> vecini[1 + MAX_N];

int s;
int distanta[1 + MAX_N];
bool inCoada[1 + MAX_N];
int nr[1 + MAX_N];
int main() {
  fin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int x, y, cost;
    fin >> x >> y >> cost;
    vecini[x].push_back(Muchie{y, cost});
  }
  for (int u = 1; u <= n; u++)
    distanta[u] = INF;
  distanta[1] = 0;
  std::queue<int> bfQ;
  bfQ.push(1);
  inCoada[1] = true;
  nr[1] = 1;
  while (!bfQ.empty() && nr[bfQ.front()] <= n) {
    int u = bfQ.front();
    bfQ.pop();
    inCoada[u] = false;
    for (Muchie e : vecini[u]) {
      if (distanta[u] + e.cost < distanta[e.vecin]) {
        distanta[e.vecin] = distanta[u] + e.cost;
        if (!inCoada[e.vecin]) {
          bfQ.push(e.vecin);
          inCoada[e.vecin] = true;
          nr[e.vecin]++;
        }
      }
    }
  }
  if (bfQ.empty()) {
    for (int i = 2; i <= n; i++)
      fout << distanta[i] << " ";
    fout << '\n';
  }
  else
    fout << "Ciclu negativ!\n";
  return 0;
}