#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

#define NMAX 50001
#define INF 0x3f3f3f3f

#define pb push_back
#define mp make_pair
#define nod first
#define cost second

using namespace std;

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

vector< pair< int, int > > G[NMAX];
vector< pair< int, int > >::iterator Vecin;
queue< int > Q;
int N, M, i, x, y, c, D[NMAX], It, ItNod[NMAX], Nod;
bool USED[NMAX];

int main()
{
    in >> N >> M;
    for( ; M--; )
    {
        in >> x >> y >> c;
        G[x].pb( mp( y, c ) );
    }

    memset( USED, false, sizeof(USED) );
    memset( D, INF, sizeof(D) );
    D[1] = 0;
    memset( ItNod, 0, sizeof(ItNod) );
    Q.push( 1 );
    USED[1] = true;

    while( !Q.empty() )
    {
        Nod = Q.front();
        Q.pop();
        USED[Nod] = false;

        for( Vecin = G[Nod].begin(); Vecin != G[Nod].end(); Vecin++ )
            if( D[(*Vecin).nod] > D[Nod] + (*Vecin).cost )
            {
                D[(*Vecin).nod] = D[Nod] + (*Vecin).cost;

                if( !USED[(*Vecin).nod] )
                {
                    Q.push( (*Vecin).nod );
                    USED[(*Vecin).nod] = true;
                    if( ++ItNod[(*Vecin).nod] > N )
                    {
                        out << "Ciclu negativ!\n";
                        return 0;
                    }
                }
            }
    }

    for( i = 2; i <= N; i++ )
        out << D[i] << ' ';
    return 0;
}