//============================================================================
// Name        : sdfdgfdg.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
# include <cstdio>
# include <fstream>
# include <iostream>
# include <algorithm>
# include <vector>
# include <queue>
# define DIM 50005
# define inf 0x3f3f3f
using namespace std;
struct nod
{
	int y,cost;
};
vector< vector< nod > > mat( DIM );
vector< int > dist( DIM, inf );
int n,m;
inline void citire()
{
	ifstream fin( "dijkstra.in" );
	fin >> n >> m;
	for( ; m; --m )
	{
		int x,y,c;
		fin >> x >> y >> c;
		mat[ x ].push_back( ( nod ) { y ,c } );

	}
}
void dijkstra( int x )
{
	queue< int > q;
	q.push( x );
	dist[ x ] = 0;
	while( !q.empty() )
	{
		int x = q.front();
		for( int i = 0; i < mat[ x ].size(); ++i )
			if( dist[ x ] + mat[ x ][ i ].cost < dist[ mat[ x ][ i ].y ] )
			{
				dist[ mat[ x ][ i ].y ] = dist[ x ] + mat[ x ][ i ].cost;
				q.push( mat[ x ][ i ].y );
			}
		q.pop();
	}
}
inline void afisare()
{
	ofstream fout( "dijkstra.out" );
	for( int i = 2; i <= n; ++i )
		if( dist[ i ] == inf )
			fout << 0 << " ";
		else
			fout << dist[ i ] << " " ;
}
int main()
{
	citire();
	dijkstra( 1 );
	afisare();
}