#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
ifstream in ("bellmanford.in");
ofstream out ("bellmanford.out");
const int NR = 50005 ;
const int oo = 50000005 ;
vector < pair < int , int > > v [ NR ] ;
vector < int > d ( NR , oo ) ;

int viz [ NR ] , n , m ;
int main ()
{
 in >> n >> m ;
 while ( m -- )
 {
     int x , y , z ;
     in >> x >> y >> z ;
     v [ x ].pb ( mp ( y , z ) ) ;
 }

 deque < int > q ;
 q.push_back ( 1 ) ;
d [ 1 ] = 0 ;

 while ( !q.empty() )
 {
     int nod = q.front() ;
     q.pop_front() ;
     viz [ nod ] ++ ;
     if ( viz [ nod ] == n + 1 )    return out << "Ciclu negativ!"  , 0 ;
     for( size_t i = 0 ; i < v [ nod ].size() ; ++ i )
     {
         if ( d [ nod ] + v [ nod ][ i ].second < d [ v [ nod ][ i ].first ] )
         {
             d [ v [ nod ][ i ].first ] = d [ nod ] + v [ nod ][ i ].second ;
             q.push_back ( v [ nod ][ i ].first ) ;
         }
     }
 }
 for ( int i = 2 ; i <= n ; ++ i )  out << d [ i ] << " " ;
 return 0 ;
}