#include <cstdio>
#include <vector>
#include <queue>
#define nmax 50001
#define INF 2000000000

using namespace std;

vector < pair < int, int > > v[nmax];
queue <int> coada;
int dist[nmax];

void init( int nr_nod, int nod_start ) {
  for ( int i = 1; i <= nr_nod; i++ )
    dist[i] = INF;
  dist[nod_start] = 0;
}

void bellmanford( int nr_nod, int nr_muchii, int nod_start ) {
  init( nr_nod, nod_start );
  coada.push( nod_start );
  for ( int i = 0; 1LL*i < 1LL * nr_nod * nr_muchii && coada.empty() == 0; i++ ) {  ///cat timp coada nu e vida si nu e sigur ca avem un ciclu negativ
    for ( int j = 0; j < v[ coada.front() ].size(); j++ ) {
      if( dist[ coada.front() ] + v[coada.front()][j].second < dist[ v[coada.front()][j].first ] ) {///daca drumul e mai mic
        dist[ v[coada.front()][j].first ] = dist[ coada.front() ] + v[ coada.front() ][j].second;
        coada.push( v[coada.front()][j].first );
      }
    }
    coada.pop();
  }
}

bool verif( int nod_start, int nr_nod ) {
  for( int i = 1; i <= nr_nod; i++ ) {
    for( int j = 0; j < v[i].size(); j++ ) {
      if( dist[ i ] + v[i][j].second < dist[ v[i][j].first ] ) ///daca se poate face un drum mai mic, inseamna ca avem ciclu negativ
        return false;
    }
  }
  return true;
}

int main() {
  int nr_nod, nr_muchii, i, x, y, c;
  FILE *fin, *fout;
  fin = fopen( "bellmanford.in", "r" );
  fscanf( fin, "%d%d", &nr_nod, &nr_muchii );
  for ( i = 0; i < nr_muchii; i++ ) {
    fscanf( fin, "%d%d%d", &x, &y, &c );
    v[x].push_back( { y, c } );
  }
  fclose( fin );
  bellmanford( nr_nod, nr_muchii, 1 );
  fout = fopen( "bellmanford.out", "w" );
  if( verif( 1, nr_nod ) == false )
    fprintf( fout, "Ciclu negativ!\n" );
  else{
    for( i = 2; i <= nr_nod; i++ )
      fprintf( fout, "%d ", dist[i] );
    fputc( '\n', fout );
  }
  return 0;
}