#include <iostream>
#include <vector>
#include <queue>

#define MAX_N 50000
const int INF = 0x7fffffff;

using namespace std ;

struct Muchie {
  int v; // vecin
  int cost;
};

vector<struct Muchie> muchii[1 + MAX_N];
int dist[1 + MAX_N];

bool inCoada[1 + MAX_N];

void bellmanFord(int s, int n) {
  queue<int> q;
  for(int u = 1; u <= n; u++)
    dist[u] = INF;
  q.push(s);
  inCoada[s] = true;
  dist[s] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    //inCoada[u] = false;
    for (Muchie e : muchii[u]) {
      if (dist[e.v] > dist[u] + e.cost) {
        dist[e.v] = dist[u] + e.cost;
        if (!inCoada[e.v]) {
          inCoada[e.v] = true;
          q.push(e.v);
        }
      }
    }
  }
}

int verificare (int n) {
  int i ;
  for (i = 1 ; i <= n ; i++ ) {
    for (Muchie e : muchii[i] ) {
      if (dist[e.v] > dist[i] + e.cost )
        return 1 ;
    }
  }
  return 0 ;
}

int main() {

  FILE *fin, *fout ;
  fin = fopen ("bellmanford.in", "r" ) ;
  fout = fopen ("bellmanford.out", "w" ) ;

  int n, m, i, nod ;
  Muchie elem ;

  fscanf (fin, "%d%d", &n, &m ) ;

  for (i = 0 ; i < m ; i++ ) {
    fscanf (fin, "%d%d%d", &nod, &elem.v, &elem.cost ) ;
    muchii[nod].push_back (elem) ;
  }

  bellmanFord(1, n);
  if (verificare(n) == 1 )
    fprintf (fout, "Ciclu negativ!") ;
  else {
    for (i = 2 ; i<= n ; i++ )
      fprintf (fout, "%d ", dist[i] ) ;
  }
  return 0;
}