#include<stdio.h>
#include<vector>
#include<queue>
#include<bitset>
#include<ctype.h>
#include<string.h>

using namespace std ;

#define dim 50010
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define INF 0x3f3f3f3f

vector < pair < int , int > > v[dim];
queue < int > q;
bitset < dim > in ;
int viz[dim];
int best[dim];
int n,m,x,y,c,cost;
void read()
{
    scanf("%d %d",&n,&m);
    for(int i=1;  i<=m;i++)
    {
        scanf("%d %d %d",&x,&y,&c);
        v[x].pb(mp(y,c));
    }

}
void afis (int a[dim] )
{
    for(int i=2  ;i<=n ; i++)
    printf("%d ",a[i] ) ;
}
void solve()
{
    memset (best , INF , sizeof(best ) ) ;
    best [1] = 0;
    for( q.push(1) ; !q.empty () ; q.pop () )
    {
        x = q.front ();
       in[x] = 0;
        for(int i=0 ; i<v[x].size() ; i++ )
        {
            y = v[x][i].fs;
            cost = v[x][i].sc;
            if ( (best [ y ] > best[x] + cost   )&& viz[ y ] <= n  )
            {
                best [ y ] = best[x] + cost;
               // printf("%d ",y);
                viz[ y ]++;
                if ( in [ y ] == 0 )
                {
                in[y] = 1;
                q.push ( y );
                }
            }
            if ( viz[y] == n )
            {
                while ( !q.empty() )
            q.pop() ;
            printf("Ciclu Negativ!\n");
            return ;
            }
        }
    }
    afis ( best ) ;
}
int main ()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    read();
    solve();
    return 0;
}