#include <fstream>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cstring>
#include <queue>

#define INF 0x3f3f3f3f
#define NMAX 50005
#define get_max(a,b) ((a)>(b)?(a):(b))
#define get_min(a,b) ((a)<(b)?(a):(b))

using namespace std;

ifstream in ( "bellmanford.in" );
ofstream out ( "bellmanford.out" );

vector < pair < int ,int > > G[NMAX] ;
queue < pair < int , int > > Bellman;
int used[NMAX] , cost[NMAX] ;
bool inQueue[NMAX];
int N , M ;

bool BellmanFord ( void ){
   Bellman.push( make_pair( 1 , 0 ) );
   memset ( cost , INF , sizeof(cost));
   cost[1] = 0 ;
   for ( ; Bellman.size(); ){
     int node = Bellman.front().first;
     int node_cost = Bellman.front().second;
     Bellman.pop();
     inQueue[node] = false;
     for ( vector < pair < int , int > > ::iterator it = G[node].begin () ; it != G[node].end() ; ++it )
          if ( node_cost + it->second < cost[it->first])
       {
           cost[it->first] = node_cost + it->second ;
           ++used[it->first];
        if ( !inQueue[it->first] ) Bellman.push(make_pair(it->first , cost[it->first])) , inQueue[it->first] = true;
        if( used[it->first] >= N )
        {
            return 0 ;

        }

     }


   }

 return 1;
}
int main ( void ){

     int i , j ;
       in >> N >> M ;
       for ( i = 1 ; i <=  M ; ++i ){
           int x , y , macost;
           in >> x >> y >> macost;
           G[x].push_back(make_pair( y , macost )) ;
       }
    if (  BellmanFord() ) {

       for ( i = 2 ; i <= N ; ++i )
                out << cost[i] << " ";
    }
    else out << "Ciclu negativ!";
   return 0 ;
}