#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

inline int next_int() {
	int d;
	scanf("%d", &d);
	return d;
}

const int V = 50000;
const int E = 250000;

int ec, eb[V], en[E], et[E], ew[E], d[V], seen[V];

int main() {
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	memset(eb, -1, sizeof eb);
	int n = next_int();
	int m = next_int();
	for (int i = 0; i < m; i++) {
		int a = next_int() - 1;
		int b = next_int() - 1;
		int c = next_int();
		et[ec] = b;
		ew[ec] = c;
		en[ec] = eb[a];
		eb[a] = ec++;
	}
	for (int i = 0; i < n; i++) {
		d[i] = 1 << 30;
	}
	priority_queue<pair<int, int> , vector<pair<int, int> > , greater<pair<int, int> > > Q;
	Q.push(make_pair(0, 0));
	while (!Q.empty()) {
		pair<int, int> p = Q.top();
		Q.pop();
		int cost = p.first;
		int u = p.second;
		if (!seen[u]) {
			seen[u] = true;
			d[u] = cost;
			for (int e = eb[u]; e != -1; e = en[e]) {
				int v = et[e];
				int w = ew[e];
				if (d[u] + w < d[v]) {
					d[v] = d[u] + w;
					Q.push(make_pair(d[u] + w, v));
				}
			}
		}
	}
	for (int i = 1; i < n; i++) {
		printf("%d ", d[i] == 1 << 30 ? 0 : d[i]);
	}
	return 0;
}