/* Spre deosebire de Dijkstra,algoritmjul lui Bellman functioneaaza si pe
grafuri cu costuri negative. Dijkstra DOAR PE grafuri orientate cu costuri
pozitive Functioneaza ca Dijkstra, dar cu mici diferente Daca se gaseste un
circuit negativ, atunci nu exista solutie(pentru ca drumul ar fi minimizat la
maxim). Algoritmul minimizeaza drumul de la nodul de start la oricare varf x
pana la obtinerea costului minim.Costurile se retin intr-un vector d,iar pentru
fiecare arc(j,k) se verifica daca minimizeaza distanta de la nodul de start la
nodul x (d[x]>d[j]+cost[j][x]),iar aceasta operatie se repeta de n ori.Pentru a
obtine 100 de puncte,imbunatatirea costului nodurilor vecine se face
introducandu-le intr-o coada in cazul scaderii costului,daca nu apar deja
*/
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define INF 0x3f3f3f3f
    using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int n, m;
vector<pair<int, int>> graf[50005];
vector<int> v;
queue<int> coada;
int d[50005];
int viz[50005];
int esteincoada[50005];
bool bellmanford(int s) {
  for (int i = 1; i <= n; i++) {
    viz[i] = 0;
    esteincoada[i] = 0;
    d[i] = INF;
  }
  d[s] = 0;
  coada.push(s);
  esteincoada[s] = 1;

  while (!coada.empty()) {
    int nodcurent = coada.front();
    viz[nodcurent]++;
    if (viz[nodcurent] >= n)
      return false;
    coada.pop();
    esteincoada[nodcurent] = 0;

    for (size_t i = 0; i < graf[nodcurent].size(); i++) {
      int vecin = graf[nodcurent][i].first;
      int cost = graf[nodcurent][i].second;
      if (d[nodcurent] + cost < d[vecin]) {
        d[vecin] = d[nodcurent] + cost;
        if (!esteincoada[vecin])
          coada.push(vecin);
      }
    }
  }
  return true;
}
int main() {
  in >> n >> m;
  for (int i = 1; i <= m; i++) {
    int x, y, c;
    in >> x >> y >> c;
    graf[x].push_back(make_pair(y, c));
  }
  if (bellmanford(1)) {
    for (int i = 2; i <= n; i++)
      out << d[i] << " ";
  } else
    out << "Ciclu negativ!";

  return 0;
}