#include <queue>
#include <utility>
#include <vector>
#include <cstdio>

#define NMAX 50000

#define graf_cost second
#define graf_urm first
#define heap_cost first
#define heap_nod second

#define inf 2099999999

#define DBG if(0)

int dist[NMAX+1];
std::priority_queue< std::pair<int, int> > heap;
std::vector<std::pair<int, int> > graf[NMAX+1];

int n, m;
void dijkstra(int start) {
	heap.push({0, start});

	while(!heap.empty()) {
		std::pair<int, int> unde_sunt = heap.top(); heap.pop();
		DBG printf("Sunt pe nodul %d cu costul %d\n", unde_sunt.heap_nod, -unde_sunt.heap_cost);
		std::pair<int, int> urmatorul;
		for(int i=0; i<graf[unde_sunt.heap_nod].size(); i++) {
			std::pair<int,int> muchie = graf[unde_sunt.heap_nod][i];

			urmatorul.heap_nod = muchie.graf_urm;
			urmatorul.heap_cost = -1 * unde_sunt.heap_cost + muchie.graf_cost;

			if(dist[urmatorul.heap_nod] > urmatorul.heap_cost) {	// update daca avem un drum mai bun
				dist[urmatorul.heap_nod] = urmatorul.heap_cost;
				DBG printf(" - Pot ajunge pe %d cu %d\n", urmatorul.heap_nod, urmatorul.heap_cost);

				urmatorul.heap_cost *= -1;	// ca sa fie sortarea buna
				heap.push(urmatorul);
			}
		}
	}
}

int main() {
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i=0; i<m; i++) {
		int a,b,cost;
		scanf("%d%d%d", &a, &b, &cost);
		graf[a].push_back({b, cost});
	}

	for(int i=1; i<=n; i++) dist[i] = inf;
	dist[1] = 0;
	dijkstra(1);

	for(int i=2; i<=n; i++) printf("%d ", dist[i]);
	printf("\n");
}