#include <queue>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define N_MAX 50011
#define oo 0x3f3f3f3f
#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;
class cmp
{
	public : bool operator() ( const int& x, const int& y ) const { return d[x] > d[y]; }
};
priority_queue< int, vector<int>, cmp > pQ;
int main( void )
{
	int N, M, x, y, c, i;
	ifstream in( "dijkstra.in" );
	for( in>>N>>M; M; --M )
	{
		in>>x>>y>>c;
		G[x].push_back( pr( y, c ) );
	}
	fill( d+2, d+N+1, oo );
	for( pQ.push( 1 ); !pQ.empty(); pQ.pop() )
	{
		x=pQ.top();
		was[x]=false;
		for( it=G[x].begin(), iend=G[x].end(); it < iend; ++it )
			if( d[it->first] > d[x]+it->second )
			{
				d[it->first]=d[x]+it->second;
				if( false == was[it->first] )
				{
					was[it->first]=true;
					pQ.push( it->first );
				}
			}
	}
	for( i=2; i <= N; ++i )
		d[i]= oo == d[i] ? 0 : d[i];
	ofstream out( "dijkstra.out" );
	copy( d+2, d+N+1, ostream_iterator<int>( out, " " ) );
	out<<'\n';
	return EXIT_SUCCESS;
}