#include <bits/stdc++.h>
#define nmax 50005
#define inf ( 1 << 30 )

using namespace std;

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

typedef pair <int, int> PI;

int N, M;

vector <int> Ad[nmax];
vector <int> Cost[nmax];

int D[nmax];

int viz[nmax];
priority_queue < PI, vector <PI>, greater <PI> > Q;

bool found;

void read()
{
    int i, x, y, z;

    fin >> N >> M;

    for ( i = 1; i <= M; ++i )
    {
        fin >> x >> y >> z;

        Ad[x].push_back( y );
        Cost[x].push_back( z );
    }

    fin.close();
}

void Dijkstra()
{
    int i, nod, w;

    D[1] = 0;
    for ( i = 2; i <= N; ++i )
         D[i] = inf;

    Q.push( make_pair( 0, 1 ) );

    while ( !Q.empty() )
    {
        nod = Q.top().second; Q.pop();

        if ( viz[nod] == N )
        {
            found = 1;
            return;
        }
        else ++viz[nod];

        for ( i = 0; i < Ad[nod].size(); ++i )
        {
            w = Ad[nod][i];

            if ( D[w] > D[nod] + Cost[nod][i] )
            {
                D[w] = D[nod] + Cost[nod][i];

                Q.push( make_pair( D[w], w ) );
            }
        }
    }
}

void out()
{
    if ( found )
    {
        fout << "Ciclu negativ!";

        return;
    }

    int i;

    for ( i = 2; i <= N; ++i )
         if ( D[i] == inf )
             fout << 0 << ' ';
         else fout << D[i] << ' ';
}

int main()
{
    read();
    Dijkstra();
    out();

    fout.close();

    return 0;
}