#include<fstream>
#include<utility>
#include<vector>

using namespace std;

#define inf 2000000000
#define max_n 50100

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n , m , A , B , C;
vector< pair<int , int> >L[max_n];
pair<int , int> nd , Arb[4*max_n];
bool Fr[max_n];
int Sol[max_n];
void read(){
	
	f>>n>>m;
	
	for( int i = 1 ; i <= m ; i++ ){
		f>>A>>B>>C;
		L[A].push_back(make_pair(B , C));
	}
	
}

pair<int , int> minim( pair<int , int> a , pair<int , int> b ){
	if( a.first < b.first )
		return a;
	return b;
}

void update( int st , int dr , int nod , int dest , pair<int , int> val ){
	
	if( st == dr ){
		Arb[nod] = val;
		return;
	}
	
	int mid = (st + dr)/2;
	
	if( dest <= mid )
		update( st , mid , 2*nod , dest , val );
	else
		update( mid+1 , dr , 2*nod+1 , dest , val );
	
	Arb[nod] = minim( Arb[2*nod] , Arb[2*nod+1] );
	
}

int main(){
	
	read();
	
	update( 1 , n , 1 , 1 , make_pair( 0 , 1 ) );
	
	for( int i = 2 ; i <= n ; i++ ){
		update( 1 , n , 1 , i , make_pair( inf , i ) );
		Sol[i] = inf;
	}
	
	for( int i = 1 ; i <= n ; i++ ){
		nd = Arb[1];
		Fr[nd.second] = 1;
		update( 1 , n , 1 , nd.second , make_pair( inf , nd.second ) );
		
		for( unsigned int j = 0 ; j < L[nd.second].size() ; j++ ){
			if( Fr[L[nd.second][j].first] == 0 && Sol[nd.second] + L[nd.second][j].second < Sol[L[nd.second][j].first] ){
				Sol[L[nd.second][j].first] = Sol[nd.second] + L[nd.second][j].second;
				update(1 , n , 1 , L[nd.second][j].first , make_pair( Sol[L[nd.second][j].first] , L[nd.second][j].first ) );
			}
		}
		
	}
	
	for( int i = 2 ; i <= n ; i++ ){
		if( Sol[i] == inf )
			Sol[i] = 0;
		g<<Sol[i]<<" ";
	}
	
	return 0;
}