#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#include <fstream>
using namespace std;
#define inf 0xfffffff

struct hnod{
	int b, c;
	hnod() {b=0;c=0;}
	hnod(int b, int c) {
		this->b = b;
		this->c = c;
	}
};
vector<hnod> g[50005];
vector<hnod> h;
int n, m, d[50005];

bool cmp(hnod n1, hnod n2){
	return n1.c > n2.c;
}

void dijkstra() {
	int x, y;
	d[1] = 0;
	for (int i = 2; i <= n; i++) {
		d[i] = inf;
	}
	h.push_back(hnod(1, 0));
	while (h.size() > 0) {
		x = h[0].b;
		pop_heap(h.begin(), h.end(), cmp);
		h.pop_back();
		for (int i = 0; i < g[x].size(); i++) {
			y = g[x][i].b;
			if (d[y] > d[x] + g[x][i].c) {
				d[y] = d[x] + g[x][i].c;
				h.push_back(hnod(y, d[y]));
				push_heap(h.begin(), h.end(), cmp);
			}
		}
	}
}

int main() {
	int a, b, c;
	
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &a, &b, &c);
		g[a].push_back(hnod(b, c));
	}
	
	dijkstra();
	
	for (int i = 2; i <= n; i++) {
		printf("%d ", d[i] == inf ? 0 : d[i]);
	}
	
	return 0;
}