#include <fstream>
#include <vector>

using namespace std ;

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

class Heap {

public :
	vector < pair < int , int > > Hheap ; 
	int sz ;
	Heap ( int N )
	{
		Hheap.resize ( 2 * N ) ;
		sz = 0 ;
	}
	void Push ( pair < long long , int > NewNode ) {
		++ sz ;
		Hheap [sz] = NewNode ;
		Up (sz) ;
	}
	pair < long long , int > Top ()
	{
		return Hheap [1] ;
	}
	void Pop ()
	{
		swap (Hheap[1] , Hheap[sz--]) ;
		Down(1) ;
	}
	bool Empty()
	{
		if ( sz != 0 )
			return false ;
		return true ;
	}
private :
	void Up ( int nod )
	{
		while ( ( nod >> 1 ) > 0 and Hheap [nod].first < Hheap [nod>>1].first ) {
			swap (Hheap [nod] , Hheap [nod >> 1]) ;
			nod >>= 1 ;
		}
	}
	void Down ( int nod ) {
		while ( (nod << 1) <= sz ) {
			if ( Hheap [nod].first > Hheap [nod<<1].first and ( (nod << 1 |1) > sz or
			Hheap [nod<<1|1].first > Hheap [nod<<1].first ) ) {
				swap (Hheap [nod], Hheap [nod<<1]) ;
				nod <<= 1 ;
			}
			else if ( ((nod <<1)|1) <= sz and Hheap [nod].first  > Hheap [nod << 1|1].first ) {
				swap (Hheap [nod], Hheap [nod <<1|1]) ;
				nod <<= 1 ;
				nod |= 1 ;
			}
			else {
				break ;
			}
		}
	}

};

Heap *H = new Heap (150014) ;

const int MAX = 5e4 + 14 ;

vector < pair < int , int > > gr [MAX] ;

long long dist [MAX] ;

int main()
{
	int n , m ;
	fin >> n >> m ;
	while ( m -- ) {
		int x , y , cost ;
		fin >> x >> y >> cost ;
		gr [x].push_back(make_pair(y,cost)) ;
	}
	for ( int i = 1 ; i <= n ; ++ i ) {
		dist [i] = 1LL << 61 ;
	}
	H->Push (make_pair (0,1)) ;
	dist [1] = 0 ;
	while ( H->Empty() == 0 ) {
		pair < int , int > cur = H->Top() ;
		H->Pop() ;

		if ( dist [cur.second] != cur.first ) {
			continue ;
		}

		for ( auto x : gr [cur.second] ) {
			if ( dist [x.first ] > cur.first + x.second ) {
				dist [x.first] = cur.first + x.second ;
				H->Push(make_pair(dist[x.first],x.first)) ;
			}
		}
	}
	for ( int i = 2 ; i <= n ; ++ i ) {
		if ( dist [i] == (1LL << 61)) {
			fout << 0 << ' ' ;
			continue ;
		}
		fout << dist [i] << ' ' ;
	}
	return 0 ;
}