// Aint

#include <iostream>
#include <vector>

using namespace std;

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


int N, M;
int cost[maxN];
bool cont[maxN];
vector < pair <int, int> > lista[maxN];

struct arb
{
	int value;
	int node;
} Aint[maxN * 3];



void update (int nod, int st, int dr, int poz, int val)
{
	if (st == dr)
	{
		Aint[nod].value = val;
		Aint[nod].node = poz;
		return;
	}
	
	int mid = (st + dr) / 2;
	
	if (mid >= poz) update (nod * 2, st, mid, poz, val);
	else update (nod * 2 + 1, mid + 1, dr, poz, val);
	
	if (Aint[nod * 2].value > Aint[nod * 2 + 1].value)
	{
		Aint[nod].value = Aint[nod * 2 + 1].value;
		Aint[nod].node = Aint[nod * 2 + 1].node;
	}
	else
	{
		Aint[nod].value = Aint[nod * 2].value;
		Aint[nod].node = Aint[nod * 2].node;
	}
}



int main()
{
	freopen ("dijkstra.in", "r", stdin);
	freopen ("dijkstra.out", "w", stdout);
	
	scanf ("%d %d", &N, &M);
	
	for (int i = 1; i <= M; ++ i)
	{
		int a, b, c;
		
		scanf ("%d %d %d", &a, &b, &c);
		
		lista[a]. PB ( MKP (b, c) );
	}
	
	for (int i = 2; i <= N; ++ i)
	{
		cost[i] = inf;
		update (1, 1, N, i, inf);
	}
	
	update (1, 1, N, 1, 0);
	
	
	for (int i = 1; i <= N; ++ i)
	{
		int nod = Aint[1].node;
		cost[nod] = Aint[1].value;
		
		update (1, 1, N, nod, inf);
		
		cont[nod] = true;
		
		for (unsigned int t = 0; t < lista[nod].size(); ++ t)
		{
			int nod2 = lista[nod][t].first;
			
			if (cont[nod2]) continue;
			
			cost[nod2] = min (cost[nod2], cost[nod] + lista[nod][t].second);
			
			update (1, 1, N, nod2, cost[nod2]);
		}
		
	}
	
	
	for (int i = 2; i <= N; ++ i) printf ("%d ", cost[i]);
	
	
	return 0;
}