#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>

using namespace std;

#define maxN 50010
#define inf (1 << 30)
#define PB push_back
#define MKP make_pair
#define f first
#define s second

int H[maxN], pozH[maxN], dim;
int Cost[maxN];
vector < pair <int,int> > list[maxN];
bool Viz[maxN];


void push (int nod)
{
	if (nod == 1) return;
	if (Cost[H[nod / 2]] <= Cost[H[nod]]) return;
	
	swap (H[nod], H[nod / 2]);
	swap (pozH[H[nod]], pozH[H[nod / 2]]);
	
	push (nod / 2);
}


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


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);
		
		list[a].PB ( MKP (b, c) );
	}
	
	H[++ dim] = 1;
	pozH[1] = 1;
	
	for (int i = 2; i <= N; ++ i)
	{
		Cost[i] = inf;
		H[++ dim] = i;
		pozH[i] = dim;
	}
	
	for (int i = 1; i <= N; ++ i)
	{
		int nod = H[1];
		Viz[nod] = true;
		
		swap (H[1], H[dim]);
		swap (pozH[H[1]], pozH[H[dim]]);
		-- dim;
		pop (1);
		
		for (unsigned int i = 0; i < list[nod].size(); ++ i)
		{
			int nod2 = list[nod][i].f, cost2 = list[nod][i].s;
			
			if (Viz[nod2]) continue;
			if (Cost[nod2] <= Cost[nod] + cost2) continue;
			
			Cost[nod2] = Cost[nod] + cost2;
			
			int pos = pozH[nod2];
			
			if (Cost[H[pos / 2]] < 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;
}