#include <vector>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <queue>

#define MAX_SIZE 50005
#define get_max( a,b) ((a)>(b)?(a):(b))
#define mk make_pair
#define INF 0x3f3f3f3f

using namespace std;

typedef vector < pair < int,int > > ::iterator vii;

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

vector <  pair < int  ,int > > G[MAX_SIZE] ;
int N , M , Cost[MAX_SIZE] ;
priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > Heap;
bool InQueue[MAX_SIZE];

void Dijkstra ( void )
{
	memset ( Cost , INF , sizeof ( Cost ) );
	Cost[1] = 0 ;
	Heap.push(mk( 1 , 0));
	for ( ; !Heap.empty() ; )
	{
		int node = Heap.top().first , val = Heap.top().second;
		Heap.pop(),InQueue[node] = false;
		for( vii it = G[node].begin();  it != G[node].end() ; ++it )
			if ( Cost[it->first] > Cost[node] + it->second )
			{
				Cost[it->first] = val + it->second;
				if( !InQueue[it->first])
				Heap.push(mk( it->first , Cost[it->first] )) , InQueue[it->first] = true;;
			}
	}
}


int main ( void )
{
	int i , j , x , y , c ;
	in >> N >> M ;
	for ( i = 1 ; i <= M ; ++i )
	{
		in >> x >> y >> c ;
		G[x].push_back(mk(y,c));
	}
	Dijkstra();
	for ( i = 2 ; i <= N ; ++i )
		out << ( Cost[i] == INF ? 0 : Cost[i] ) << " ";
	in.close();
	out.close();
	return 0 ;
}