#include <queue>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <algorithm>
#define N_MAX 50011
#define oo 1<<30
#define pr pair< int, int >

using namespace std;

int d[N_MAX];
vector< pr > G[N_MAX];

void Dijkstra( int start )
{
	pr x;
	bool used[N_MAX]={false};
	priority_queue< pr, vector<pr>, greater<pr> > pQ;
	vector< pr >::const_iterator it, iend;

	d[start]=0;
	for( pQ.push( pr( 0, start ) ); !pQ.empty();  )
	{
		x=pQ.top(); pQ.pop();
		if( true == used[x.second] )
			continue;
		used[x.second]=true;
		for( it=G[x.second].begin(), iend=G[x.second].end(); it < iend; ++it )
			if( d[it->first] > d[x.second]+it->second )
			{
				d[it->first]=d[x.second]+it->second;
				pQ.push( pr( d[it->first], it->first ) );
			}		
	}
}
int main()
{
	int N, M, x, y, c, i;
	ifstream in( "dijkstra.in" );
	ofstream out( "dijkstra.out" );
	
	for( in>>N>>M; M; --M )
	{
		in>>x>>y>>c;
		G[x].push_back( pr( y, c ) );
	}
	fill( d, d+N+1, oo );
	Dijkstra( 1 );
	for( i=2; i <= N; ++i )
		out<<( oo == d[i] ? 0 : d[i] )<<' ';
	out<<'\n';	
	return EXIT_SUCCESS;
}