#include <cstdio>
#include <vector>
#include <cstring>

#define NMAX 50005
#define pb push_back
#define INF 0x3f3f3f3f

using namespace std;

typedef struct { int N1; int N2; int Cost; } Muchie;
vector< Muchie > E;
vector< Muchie >::iterator MC;
Muchie MCt;

int N, M, COST[NMAX], It;
bool Continuare;

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

    scanf("%d%d", &N, &M);
    while( M-- )
    {
        scanf("%d%d%d", &MCt.N1, &MCt.N2, &MCt.Cost);
        E.pb( MCt );
    }

    memset( COST, INF, sizeof(COST) );
    COST[1] = 0;

    for( Continuare = true, It = 1; It < N && Continuare; It++ )
        for( Continuare = false, MC = E.begin(); MC != E.end(); MC++ )
            if( COST[(*MC).N2] > COST[(*MC).N1] + (*MC).Cost )
            {
                COST[(*MC).N2] = COST[(*MC).N1] + (*MC).Cost;
                Continuare = true;
            }

    for( MC = E.begin(); MC != E.end(); MC++ )
        if( COST[(*MC).N2] > COST[(*MC).N1] + (*MC).Cost )
        {
            printf("Ciclu negativ!\n");
            return 0;
        }

    for( It = 2; It <= N; It++ )
        printf("%d ", COST[It]);
    printf("\n");

    return 0;
}