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

const int INF = 1e9;

const int MAXN = 1e5;
std::vector<std::pair<int, int>> adj[MAXN];
int dist[MAXN];

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

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

  for( int i = 0; i < m; i++ ){
    int a, b, cost;
    fscanf( fin, "%d%d %d", &a, &b, &cost );
    a--; b--;
    adj[a].emplace_back( b, cost );
  }

  for( int i = 0; i < n; i++ )
    dist[i] = +INF;

  int iter = 0, maxiter = n * m + 4;
  std::queue<int> q;
  dist[0] = 0;
  q.emplace( 0 );
  while( iter < maxiter && !q.empty() ){
    int u = q.front();
    q.pop();

    iter++;

    for( auto [v, cost]: adj[u] )
      if( dist[u] + cost < dist[v] ){
        dist[v] = dist[u] + cost;
        q.push( v );
      }
  }

  if( iter < maxiter ){
    for( int i = 1; i < n; i++ )
      fprintf( fout, "%d ", dist[i] == +INF ? 0 : dist[i] );
    fputc( '\n', fout );
  }else{
    fprintf( fout, "Ciclu negativ!" );
  }
  
  fclose( fin );
  fclose( fout );
  return 0;
}