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

#define NMAX 50001
#define INF 10002

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

using namespace std;

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

vector< pair < int, int > > Graph [NMAX] ;
vector< pair < int, int > > ::iterator vec ;

queue< int > Q ;

int N, M, i, x, y, c, D[NMAX], It, iterari_nod [NMAX], Nod;
bool in_queue [NMAX];

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

    memset( in_queue , false , sizeof(in_queue) ) ; //initial nu avem noduri in coada
    memset( D , INF , sizeof(D) ) ; //toate distantele sunt infinit
    D[1] = 0 ; //mai putin cea pana la sursa
    memset( iterari_nod , 0 , sizeof(iterari_nod) ) ; //nu s-a trecut niciodata prin niciun nod
    Q.push( 1 ) ; //introducem nodul 1 in coada
    in_queue [1] = true;

    while( !Q.empty() )
    {
        Nod = Q.front();
        Q.pop();
        in_queue [Nod] = false; // scoatem nodul din coada

        for( vec = Graph [Nod].begin(); vec != Graph [Nod].end(); vec ++ ) // iteram prin vecinii nodului
            if( D [ (*vec).nod ] > D[Nod] + (*vec).cost ) // incercand sa minimizam distanta pana la acestia
            {
                D [ (*vec).nod ] = D[Nod] + (*vec).cost ;

                if( !in_queue [(*vec).nod] ) // daca nodul nu se afla in coada
                {
                    Q.push( (*vec).nod ) ; // il introducem
                    in_queue [(*vec).nod] = true ;
                    if( ++ iterari_nod [ (*vec).nod ] > N ) // daca s-a trecut de mai mult de N ori prin el
                    {
                        fout << "Ciclu negativ!\n"; // inseamna ca in graf exista un ciclu negativ
                        return 0;
                    }
                }
            }
    }

    for( i = 2; i <= N; ++ i )
        fout << D[i] << ' '; // distantele de la nodul 1( sursa ) pana la celelalte noduri

    return 0;
}