#include <fstream>
#include <algorithm>
#include <climits>
#include <queue>
#include <vector>
#include <bitset>
using namespace std;

#define Nmax 50002

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

int N, M;
int Dist[Nmax], Used[Nmax];
vector < pair < int, int > > G[Nmax];
queue < int > Q;
bitset < Nmax > inQ;

void BellmanFord(){

    for( int i = 2; i <= N; ++i )
        Dist[i] = INT_MAX;

    Q.push( 1 );
    inQ[1] = 1;
    Used[1]++;

    while( !Q.empty() ){
        int nod = Q.front();
        Q.pop();
        inQ[nod] = 0;

        vector < pair < int, int > >  :: iterator it;

        for( it = G[nod].begin(); it != G[nod].end(); ++it ){
            int d = Dist[nod] + it->second;

            if( d < Dist[it->first] ){
                Dist[it->first] = d;

                Used[it->first]++;
                if( Used[it->first] >= N ){
                    fout << "Ciclu negativ!";
                    return;
                }

                if( !inQ[it->first] ){
                    Q.push( it->first );
                    inQ[it->first] = 1;
                }
            }
        }
    }

    for( int i = 2; i <= N; ++i )
        fout << Dist[i] << " ";
}

int main(){

    fin >> N >> M;

    int x, y, c;

    while( M-- ){
        fin >> x >> y >> c;
        G[x].push_back( make_pair( y, c ) );
    }

    BellmanFord();

    return 0;
}