#include <fstream>
#include <vector>
#include <queue>

#define IN "bellmanford.in"
#define OUT "bellmanford.out"

#define f first
#define s second

#define mp make_pair
#define pb push_back

#define p pop
#define pu push

const int MAX = 250014 ;
const int inf = 1 << 30 ;

using namespace std;

ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;

typedef pair < int , int > P ;

vector < P > gr [ MAX ] ;

queue < int > q ;

int d [ MAX ] , fv [ MAX ] , n , m ;

bool bellmanford ( ) ;

int main()
{
    fin >> n >> m ;
    for ( register int i = 1 ; i <= m ; ++ i ){
        int x , y , z ;
        fin >> x >> y >> z ;
        gr [ x ].pb ( mp ( y , z ) ) ;
    }
    for ( register int i = 2 ; i <= n ; ++ i )
        d [ i ] = inf ;
    if ( bellmanford () )
        fout << "Ciclu negativ!\n" ;
    else{
        for ( register int i = 2 ; i <= n ; ++ i )
            fout << d [ i ] << " " ;
    }
    return 0;
}

bool bellmanford ( ){
    q.pu ( 1 ) ;
    fv [ 1 ] = 1 ;
    while ( !q.empty ( ) ){
        int nod = q.front ( ) ;
        q.p ( ) ;
        for ( auto x : gr [ nod ] ){
            int urm = x.f ;
            int cost = x.s ;
            if ( d [ nod ] + cost < d [ urm ] ){
                d [ urm ] = d [ nod ] + cost ;
                fv [ urm ] ++ ;
                q.pu ( urm ) ;
                if ( fv [ urm ] == n )
                    return 1 ;
            }
        }
    }
    return 0 ;
}