#include <iostream>
#include <stdio.h>
#include <queue>
#include <vector>

#define NMAX 50001
#define INFINIT 1000000001

struct muchie {
  int nod ;
  int cost ;
};

struct nd {
  int nod ;
};

using namespace std;

queue <nd> q ;
vector <muchie> mat [ NMAX + 1 ] ;
int dist [ NMAX + 1 ] ;

void bellmanford (int s, int n ) {
  q.push({1}) ;
  dist[1] = 0 ;
  for (int i = 2 ; i <= n ; i++ )
    dist[i] = INFINIT ;
  while (!q.empty()) {
    nd first = q.front() ;
    q.pop() ;
    for (muchie elem : mat[first.nod] ) {
      if (dist[first.nod] + elem.cost < dist[elem.nod] ) {
        dist[elem.nod] = dist[first.nod] + elem.cost ;
        q.push({elem.nod}) ;
      }
    }
  }
}

int main() {

  FILE *fin, *fout ;
  fin = fopen ("bellmanford.in", "r" ) ;
  fout = fopen ("bellmanford.out", "w" ) ;
  int n, a, b, c, m, ok, i ;
  fscanf (fin, "%d%d", &n, &m ) ;
  for (i = 0 ; i < m ; i++ ) {
    fscanf (fin, "%d%d%d", &a, &b, &c ) ;
    mat[a].push_back({b, c}) ;
  }
  bellmanford(1, n) ;
  ok = 0 ;
  for (i = 1 ; i <= n ; i++ ) {
    for (muchie elem : mat[i] )
      if (dist[elem.nod] > elem.cost + dist[i] )
        ok = 1 ;
  }
  if (ok == 1 )
    fprintf (fout, "Ciclu negativ!" ) ;
  else
    for (i = 2 ; i <= n ; i++ )
      fprintf (fout, "%d ", dist[i] ) ;
  return 0;
}