#include <bits/stdc++.h>
using namespace std;

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

const int INF = 1e9 ;

vector < pair < int , int > > g[50005] ;

void solve ()
{
    int n , m ;
    fin >> n >> m ;
    for ( int i = 1 ; i <= m ; i ++ )
    {
        int x , y , c ;
        fin >> x >> y >> c ;
        g[x].push_back({y,c}) ;
    }
    vector < int > dist ( n + 1 , INF ) ;
    vector < bool > inqueue ( n + 1 , false ) ;
    vector < int > cnt( n + 1 , 0 ) ;
    queue < int > q ;

    dist[1] = 0 ;
    q.push(1) ;
    inqueue[1] = true ;
    bool ok = 0 ;
    while ( ! q.empty() && ok == 0 )
    {
        int u = q.front() ;
        q.pop() ;
        inqueue[u] = false ;

        for ( auto it : g[u] )
        {
            int v = it.first ;
            int pr = it.second ;
            if ( dist[u] + pr < dist[v] )
            {
                dist[v] = dist[u] + pr ;
                if ( !inqueue[v] == true )
                {
                    q.push(v) ;
                    inqueue[v] = true ;
                    cnt[v] ++ ;
                    if ( cnt[v] >= n )
                    {
                        fout << "Ciclu negativ!" ;
                        ok = 1 ;
                        break ;
                    }
                }
            }
        }
    }
    if ( ok == 0 )
        for ( int i = 2 ; i <= n ; i ++ )
            fout << dist[i] << " " ;
}

int main()
{
    std :: ios_base :: sync_with_stdio(false ) ;
    fin.tie(0) ;
    fout.tie(0) ;
    solve () ;

    return 0;
}