#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define NMAX 50005
#define INF 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define nod first
#define cost second

vector< pair< int, int > > G[NMAX];
int D[NMAX];
int N, M, i, x, y, c;
struct comp
{
	bool operator() (const int &x, const int &y)
	{
		return D[x] > D[y];
	}
};
priority_queue< int, vector< int >, comp > Q;

int main()
{
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	
	scanf("%d%d", &N, &M );
	for( ; M--; )
	{
		scanf("%d%d%d", &x, &y, &c );
		G[x].pb( mp( y, c ) );
	}
	
	memset( D, INF, sizeof(D) );
	D[1] = 0;
	Q.push( 1 );
	
	while( !Q.empty() )
	{
		int Nod = Q.top();
		Q.pop();
		for( vector< pair< int, int > >::iterator it = G[Nod].begin(); it != G[Nod].end(); ++it )
			if( D[(*it).nod] > D[Nod] + (*it).cost )
			{
				D[(*it).nod] = D[Nod] + (*it).cost;
				Q.push( (*it).nod );
			}
	}
	
	for( i = 2; i <= N; ++i )
		printf("%d ", ( D[i] == INF ) ? 0 : D[i] );
	printf("\n");
	
	return 0;
}