///Gergely David
//Colegiul National Petru Rares Beclean

#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <algorithm>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <deque>
#include <queue>
#include <bitset>
#include <iomanip>
#include <stack>
#include <sstream>
#include <cstring>
#include <string>
#include <cassert>


using namespace std ;

const char inname[] = "bellmanford.in" ;
const char outname[] = "bellmanford.out" ;



const int NMAX = 50010;
const int MMAX = 250010 ;
const int INF = 0x3f3f3f3f ;


struct muhie {
long a, b, c;
}E[NMAX];


ifstream in(inname) ;
ofstream out(outname) ;

long N, M, K, left, right, cost[NMAX], F[NMAX] ;
vector <long> V[NMAX] ;
vector <pair < long, long > > H ;

void READ() ;
void SOLVE() ;
void OUT() ;


inline int max(int a, int b)
{
	if(a > b) return a ;
	else return b ;
}
inline int min(int a, int b)
{
	if(a < b) return a ;
	else return b ;
}

inline void READ() {

in >> N >> M ;

for(long i = 1 ; i <= M ; ++ i)
{
    in >> E[i].a >> E[i].b >> E[i].c ;
    V[E[i].a].push_back(i) ;
}


}

inline void INIT() {

cost[1] = 0;

for(long i = 2; i <= N ; ++ i)
    cost[i] = INF ;

    H.push_back(make_pair(0, 1)) ;
    make_heap(H.begin(), H.end()) ;


}

inline void SOLVE() {


    pair <long, long> per;
    long nod, poz;
    long long pas = 0;

    while(H.size() && pas <= 1LL * N *M)
    {

        ++ pas ;
        pop_heap(H.begin(), H.end()) ;
        per = H.back() ;
        H.pop_back() ;
        nod = per.second ;
        F[nod] = 0 ;

        for(long j = 0 ; j< V[nod].size() ; ++ j)
        {

            poz = V[nod][j] ;

            if(cost[E[poz].a] + E[poz].c < cost[E[poz].b])
            {
                cost[E[poz].b] = cost[E[poz].a] + E[poz].c ;
                if(!F[E[poz].b])
                {
                    F[E[poz].b] = 1 ;
                    H.push_back(make_pair(-cost[E[poz].b], E[poz].b) ) ;
                    push_heap(H.begin(), H.end()) ;
                }

            }
        }
    }



}


inline long VERIF_NEGATIV() {

for(long i = 2 ; i <= M ; ++ i)
    if(cost[ E[i].a ] + E[i].c < cost[ E[i].b ] )
        return 1 ;
    else return 0 ;
}

inline void OUT() {

if(VERIF_NEGATIV())
    out << "Ciclu Negativ!" << '\n' ;
    else
        for(long i = 2 ; i <= N ; ++ i)
            out << cost[i] << ' ' ;
    out << '\n' ;

}

int main()
{
	READ() ;
	INIT() ;
	SOLVE() ;
	OUT() ;
	in.close() ;
	out.close() ;
	return  0 ;
}