#include <cstdio>
#include <queue>
#include <vector>

using namespace std ;

struct NOD { int nr , cost ; } ;

const int NMAX = 50005 ;
const int INF = NMAX*1001 ;
vector<NOD> mat[NMAX] ;
priority_queue<pair <int,int> > h ; 
bool f[NMAX];
int d[NMAX];
int main ( )
{
	
	freopen ( "dijkstra.in", "r" , stdin ) ;
	freopen ( "dijkstra.out", "w", stdout ) ;
	
	int N , M ;
	int x , y , cost , i ;
	
	scanf ( "%d%d", & N , & M ) ;

	for ( i = 1 ; i <= M ; ++ i )
	{
		scanf ( "%d%d%d", & x , & y , & cost ) ;
		mat[x].push_back ( (NOD){y,cost} ) ;
	}
	
	for ( i = 1 ; i <= N ; ++ i )
		d[i] = INF ;
	
	d[1] = 0 ;
	pair<int,int> aux ;
	aux.first = 0 ;
	aux.second = 1 ;
	h.push ( aux ) ;
	for ( i = 1 ; i <= N ; ++ i )
	{
		while ( !h.empty() && f[x=h.top().second] )
			h.pop () ;
		
		if ( h.empty () )
			break;
		
		h.pop () ;
		f[x] = true ;
		for ( size_t j = 0 ; j < mat[x].size() ; ++ j )
		{
			y = mat[x][j].nr ;
			if ( d[y] > d[x] + mat[x][j].cost )
			{
				d[y] = d[x] + mat[x][j].cost ;
				aux.first = -d[y] ;
				aux.second = y ;
				h.push ( aux ) ;
			}
		}
	}
	
	for ( i = 2 ; i <= N ; ++ i )
		printf ( "%d ", d[i] ) ;
	
	return 0 ;
}