#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
#define maxn 50001
#define oo 0x3f3f3f3f
using namespace std;
const char iname[] = "dijkstra.in";
const char oname[] = "dijkstra.out";
ifstream fin(iname);
ofstream fout(oname);
int N , M , i , j , x , y , c;
int d[ maxn ];
struct muchii
{
	int x , cost;
};
struct cmp
{
    bool operator()( const int &a, const int &b )const
    {
		if( d[ a ] > d[ b ] ) return 1;
		return 0;
    }
};
vector < muchii > v[ maxn ];
priority_queue < int , vector < int > , cmp > Q;
int main()
{
	fin >> N >> M;
	muchii aux;
	for ( i = 1; i <= M; ++i )
	{
		fin >> x >> aux.x >> aux.cost;
		v[ x ].push_back( aux );
	}
	memset ( d , oo , sizeof( d ) );
	d[ 1 ] = 0;
	Q.push( 1 );
	vector < muchii > :: iterator it , final;
	while ( !Q.empty() )
	{
		x = Q.top();
		Q.pop();
		it = v[ x ].begin();
		final = v[ x ].end();
		for ( ; it != final ; ++it )
		{
			if ( d[ x ] + it -> cost < d[ it -> x ] )
			{
				d[ it -> x ] = d[ x ] + it -> cost;
				Q.push( it -> x );
			}
		}
	}
	for ( i = 2; i <= N; ++i )
	{
		if ( d[ i ] != oo ) 
			fout << d[ i ] << ' ';
		else
			fout << 0 << ' ';
	}
	fout << '\n';
    return 0;
}