// SET

#include <iostream>
#include <vector>
#include <set>

using namespace std;

#define maxN 50005
#define PB push_back
#define MP make_pair
#define inf (1 << 30)

set < pair <int, int> > S;
vector < pair <int, int> > lista[maxN];
int cost[maxN];
bool cont[maxN];


int main()
{
	freopen ("dijkstra.in", "r", stdin);
	freopen ("dijkstra.out", "w", stdout);
	
	int N, M;
	
	scanf ("%d %d", &N, &M);
	
	while (M --)
	{
		int a, b, c;
		
		scanf ("%d %d %d", &a, &b, &c);
		
		lista[a]. PB ( MP (b, c) );
	}
	
	for (int i = 2; i <= N; ++ i)
	{
		cost[i] = inf;
		S.insert ( MP (inf, i) );
	}
	
	S.insert (MP (0, 1));
	
	for ( ; ! S.empty() ; )
	{
		int nod = (*S.begin()).second;
		
		S.erase (*S.begin());
		
		cont[nod] = true;
		
		for (unsigned int t = 0; t < lista[nod].size(); ++ t)
		{
			int node = lista[nod][t].first;
			
			if (cont[node]) continue;
			
			if (cost[node] > cost[nod] + lista[nod][t].second)
			{
				cost[node] = cost[nod] + lista[nod][t].second;
				S.insert ( MP (cost[node], node) );
			}
		}
	}
	
	
	for (int i = 2; i <= N; ++ i)
		if (cost[i] != inf) printf ("%d ", cost[i]);
		else printf ("0 ");
	
	
	return 0;
}