#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 250005
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int oo = (1 << 30);

int n, m, d[NMAX], ccl[NMAX];
vector<pair<int, int>> gr[NMAX];
bool in_q[NMAX], ciclu;

void citire() {
  fin >> n >> m;
  for (int i = 0; i < m; i++) {
    int x, y, cost;
    fin >> x >> y >> cost;
    gr[x].push_back(make_pair(y, cost));
  }
}

struct compara {
  bool operator() (int x, int y) {
    return d[x] > d[y];
  }
};

queue<int> q;

void BellmanFord(int nodStart) {
  for (int i = 1; i <= n; i++)
    d[i] = oo;
  d[nodStart] = 0;
  q.push(nodStart);
  
  while (!q.empty() && !ciclu) {
    int nodCurent = q.front();
    q.pop();
    ccl[nodCurent]++;
    if (ccl[nodCurent] > n) {
      ciclu = true;
      return;
    }
    
    for (int i = 0; i < gr[nodCurent].size(); i++) {
      int vecin = gr[nodCurent][i].first;
      int cost = gr[nodCurent][i].second;
      
      if (d[nodCurent] + cost < d[vecin]) {
        d[vecin] = d[nodCurent] + cost;
        q.push(vecin);
      }
    }
  }
}

void afisare() {
  if (ciclu)
    fout << "Ciclu negativ!";
  else
    for (int i = 2; i <= n; i++)
      if (d[i] != oo)
        fout << d[i] << " ";
}

int main(int argc, const char * argv[]) {
  citire();
  BellmanFord(1);
  afisare();
}