#include <cstdio>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

#define Nmax 50010
vector <pair<long,long> >ad[Nmax] ;
queue <long> q ;
long T[Nmax] , n , m , x , y , c , cnt_in_queue[Nmax];
bool in_queue[Nmax] , negativ ;

void BellManFord ( long start )
{
    q.push(start);
    in_queue[start] = true ;
    memset(T,0x3f,sizeof(T)) ;
    T[start] = 0 ;
    while ( !q.empty() )
    {
        long nod = q.front();
        q.pop();
        in_queue[nod] = false ;
        for ( long i = 0 ; i < ad[nod].size() ; ++i )
        {
            if ( T[nod] + ad[nod][i].second < T[ad[nod][i].first] )
            {
                negativ = false ;
                T[ad[nod][i].first] = T[nod] + ad[nod][i].second ;
                if ( !in_queue[ad[nod][i].first]  )
                {
                    if ( cnt_in_queue[ad[nod][i].first] > n )
                    {
                        negativ = true ;
                    }
                    else
                    {
                        q.push(ad[nod][i].first) ;
                        in_queue[ad[nod][i].first] = true ;
                        cnt_in_queue[ad[nod][i].first]++;
                    }
                }
            }
        }
    }
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);

    scanf("%d %d",&n,&m);
    for ( long i = 1 ; i <= m ; i++ )
    {
        scanf("%d %d %d",&x,&y,&c);
        ad[x].push_back(make_pair(y,c));
    }
    BellManFord(1) ;
    if ( negativ == true )
    {
        printf("Ciclu negativ!\n");
        return 0 ;
    }
    else for ( long i = 2 ; i <= n ; i++ )
    {
        printf("%d ",T[i]) ;
    }
}