#include <fstream>
#include <vector>

using namespace std ;

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

class Heap {

public :
	vector < pair < long long , 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 ) {
				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 ((int)3e5) ;

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 << -1 << ' ' ; 
			continue ; 
		}
		fout << dist [i] << ' ' ; 
	}
	return 0 ; 
}