#include <fstream>
#include <vector>
#include <cstring>

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

using namespace std;

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

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()
{
    in >> N >> M;
    while( M-- )
    {
        in >> 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 )
        {
            out << "Ciclu negativ!\n";
            return 0;
        }

    for( It = 2; It <= N; It++ )
        out << COST[It] << ' ';
    out << '\n';

    return 0;
}