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

using namespace std;

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

int Cost[maxN];
bool Viz[maxN];
vector <pair <int, int> > G[maxN];
vector <pair <int, int> > :: iterator it;
int H[maxN], pozH[maxN], dim;


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


void pop (int nod)
{
	int f1 = nod * 2, f2 = nod * 2 + 1;
	int nodmin = nod;
	
	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);
}


inline int get_Min ()
{		
	int node = H[1];
	
	Viz[node] = true;
	swap (H[1], H[dim]);
	swap (pozH[H[1]], pozH[H[dim]]);
	-- dim;
	
	return node;
}


int main()
{
	freopen ("dijkstra.in", "r", stdin);
	freopen ("dijkstra.out", "w", stdout);
	
	int N, M;
	
	scanf ("%d %d", &N, &M);
	
	while (M --)
	{
		int x, y, c;
		scanf ("%d %d %d", &x, &y, &c);
		
		G[x].PB ( MKP (y, c) );
	}
	
	for (int i = 2; i <= N; ++ i)
	{
		Cost[i] = inf;
		H[++ dim] = i;
		pozH[i] = dim;
	}
	
	H[++ dim] = 1;
	push (dim);
	
	for (int i = 1; i <= N; ++ i)
	{
		int nod = get_Min();
		
		for (it = G[nod].begin(); it != G[nod].end(); ++ it)
		{
			int nod2 = it -> NODE, cost2 = it -> COST;
			
			if (Viz[nod2]) continue;
			if (Cost[nod2] <= Cost[nod] + cost2) continue;
			
			Cost[nod2] = Cost[nod] + cost2;
			
			int posH = pozH[nod2];
			
			if (Cost[H[posH]] >= Cost[H[posH / 2]]) pop (posH);
			else push (posH);
		}
	}
	
	for (int i = 2; i <= N; ++ i) printf ("%d ", Cost[i]);
	
	return 0;
}