// This program was written on 24.03.2022
// for problem bellmanford
// by Mircea Rebengiuc

#include <stdio.h>
#include <ctype.h>

#include <queue> // coada alocata dinamic
#include <vector> // vector alocat dinamic

#define MAXN 50000
#define MAXM 250000
#define INF 2000000000

std::queue<int> q;
std::vector<std::pair<int, int>> adj[MAXN];

int dist[MAXN];

FILE *fin, *fout;

static inline int fgetint(){
  int n = 0, ch, semn = 1;

  while( isspace(ch = fgetc(fin)) );
  if( ch == '-' ){
    semn = -1;
    ch = fgetc(fin);
  }
  do
    n = n * 10 + ch - '0';
  while( isdigit(ch = fgetc(fin)) );

  return n * semn;
}

int main(){
  fin  = fopen( "bellmanford.in",  "r" );
  fout = fopen( "bellmanford.out", "w" );
  
  int n, m, i, a, nrloop;
  std::pair<int, int> e;
  
  n = fgetint();
  m = fgetint();
  for( i = 0 ; i < m ; i++ ){
    a = fgetint() - 1;

    e.first = fgetint() - 1;
    e.second = fgetint();

    adj[a].push_back( e );
  }
  
  dist[0] = 0;
  for( i = 1 ; i < n ; i++ )
    dist[i] = +INF;
  
  q.push( 0 );
  nrloop = n * m;
  while( !q.empty() && (nrloop--) ){
    a = q.front();
    q.pop();
    
    for( std::pair<int, int> f : adj[a] )
      if( dist[a] + f.second < dist[f.first] ){
        dist[f.first] = dist[a] + f.second;
        q.push( f.first );
      }
  }
  
  if( !q.empty() ){
    fputs( "Ciclu negativ!\n", fout );
  }else{
    for( i = 1 ; i < n ; i++ )
      fprintf( fout, "%d ", dist[i] );
    fputc( '\n', fout );
  }
  
  fclose( fin );
  fclose( fout );
  return 0;
}