#include <stdio.h>
#include <assert.h>
#include <vector>
#include <set>

using namespace std;

#define PII pair<int, int>
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define INF 2000000001

int N, M, dist[50005];
vector<PII> G[50005];
set<int> LIST[50005];
set<PII> HEAP;

void dijkstra(int sursa)
{
	int i, j, ind, sz, x, cost;
	set<PII>::iterator head;
	
	for (i = 2; i <= N; ++i)
	{
		dist[i] = INF;
		HEAP.insert( mp(dist[i], i) );
	}
	
	dist[sursa] = 0;
	HEAP.insert( mp(dist[sursa], sursa) );
	for (i = 1; i < N; ++i)
	{
		head = HEAP.begin();
		ind = head->s;
		HEAP.erase(head);
		
		for (sz = G[ind].size(), j = 0; j < sz; ++j)
		{			
			x = G[ind][j].f;
			cost = G[ind][j].s;
			if (dist[ind] + cost < dist[x])
			{
				head = HEAP.find( mp(dist[x], x) );
				HEAP.erase(head);
				dist[x] = dist[ind] + cost;
				HEAP.insert( mp(dist[x], x) );
			}			
		}
	}
}

int main(void)
{
	int i, j, c;
	
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);

	scanf("%d %d", &N, &M);
	assert(1 <= N && N <= 50000);
	assert(1 <= M && M <= 500000);
	for (; M; --M)
	{
		scanf("%d %d %d", &i, &j, &c);
		assert(1 <= i && i <= N && 1 <= j && j <= N);
		assert(0 <= c && c <= 1000);
		G[i].pb( mp(j, c) );
		if (LIST[i].find(j) != LIST[i].end())
			for (; ;);		
		LIST[i].insert(j);
	}

	dijkstra(1);
	
	for (i = 2; i <= N; ++i)
		printf("%d ", (dist[i] == INF) ? (0) : (dist[i]) );
	printf("\n");
	
	return 0;
}