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

using namespace std;

int d[N_MAX];
bool was[N_MAX];
vector< pr > G[N_MAX];
vector< pr >::const_iterator it, iend;
priority_queue< pr, vector<pr>, greater<pr> > pQ;

int main()
{
	pr vertex;
	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 );
	d[1]=0;
	for( pQ.push( pr( 0, 1 ) ); !pQ.empty(); )
	{
		vertex=pQ.top(); pQ.pop();
 		if( true == was[vertex.second] )
			continue;
		was[vertex.second]=true;
		for( it=G[vertex.second].begin(), iend=G[vertex.second].end(); it < iend; ++it )
			if( d[it->first] > vertex.first + it->second )
			{
				d[it->first]=vertex.first+it->second;
				pQ.push( pr( d[it->first], it->first ) );
			}
	}
	for( i=2; i <= N; ++i )
		out<<( oo == d[i] ? 0 : d[i] )<<' ';
	out<<'\n';
	return EXIT_SUCCESS;
}