// Heap

#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

#define maxN 50005
#define inf (1 << 30)
#define PB push_back
#define MKP make_pair
#define tata(nod) (nod / 2)


int H[maxN], poz[maxN], cost[maxN];
vector < pair <int, int> > lista[maxN];
bool cont[maxN];
int dimH;


void push (int nod)
{
	if (nod == 1) return;
	if (cost[H[nod]] >= cost[H[tata(nod)]]) return;
	
	swap (H[nod], H[tata(nod)]);
	swap (poz[H[nod]], poz[H[tata(nod)]]);
	
	push (tata (nod));
}


void pop (int nod)
{
	int f1 = nod * 2, f2 = nod * 2 + 1;
	int nodmin = nod;
	
	if (f1 <= dimH && cost[H[f1]] < cost[H[nodmin]]) nodmin = f1;
	if (f2 <= dimH && cost[H[f2]] < cost[H[nodmin]]) nodmin = f2;
	
	if (nodmin == nod) return;
	
	swap (H[nod], H[nodmin]);
	swap (poz[H[nod]], poz[H[nodmin]]);
	
	pop (nodmin);
}


int main()
{
	freopen ("dijkstra.in", "r", stdin);
	freopen ("dijkstra.out", "w", stdout);
	
	int N, M;
	
	scanf ("%d %d", &N, &M);
	
	for (int i = 1; i <= M; ++ i)
	{
		int a, b, costt;
		
		scanf ("%d %d %d", &a, &b, &costt);
		
		lista[a] . PB ( MKP (b, costt) );
	}

	H[++ dimH] = 1;
	poz[1] = 1;
	
	for (int i = 2; i <= N; ++ i)
	{
		cost[i] = inf;
		
		H[++ dimH] = i;
		
		poz[i] = dimH;
	}
	
	for (int i = 1; i <= N; ++ i)
	{
		int nod = H[1];
		
		cont[nod] = true;
		
		swap (H[1], H[dimH]);
		swap (poz[H[1]], poz[H[dimH]]);
		-- dimH;
		
		pop (1);
		
		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;
				
				int pos = poz[node];
				
				if (cost[H[tata(pos)]] < cost[H[pos]]) pop (pos);
				else push (pos);
			}
		}
	}
	
	for (int i = 2; i <= N; ++ i)
		if (cost[i] != inf) printf ("%d ", cost[i]);
		else printf ("0 ");
	
	return 0;
}