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

#define NMax 500001
#define INF 0x3f3f3f3f

#define nod first
#define cost second

using namespace std;

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

vector < pair <int,int> > G[NMax];
vector < pair <int,int> > :: iterator it;
queue <int> Q;
int N, M, i, x, y, c, D[NMax], ItNod[NMax], Nod, start;
bool fv[NMax];

int main()
{
    fin>>N>>M;

    for( int i = 1 ; i <= M ; i++ )
    {
        fin>>x>>y>>c;
        G[x].push_back( make_pair(y,c) );
    }

    memset( D, INF, sizeof( D ) );

    start = 1;
    D[start] = 0;

    Q.push(start);
    fv[start]=true;

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

        for( it = G[ Nod ].begin( ); it != G[ Nod ].end( ); it++ )
        {
            if( D[ ( *it ).nod ] > D[ Nod ] + ( *it ).cost  )
            {
                D[ (*it).nod ] = D[ Nod ] + ( *it ).cost;
                if( !fv[ (*it).nod ] )
                {
                    Q.push( (*it).nod );
                    fv[ (*it).nod ] = true;
                    if( ++ItNod[ ( *it ).nod ] > N )
                    {
                        fout<<"Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
        Q.pop( );
    }
    for( int i = 2; i <= N ; i++ )
    {
        fout << D[ i ] <<" ";
    }



    fin.close();
    fout.close();
    return 0;
}