#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = a; i < b; i++)
#define TRvi(c, it) for (vi::iterator it = c.begin(); it != c.end(); it++)
#define TRvii(c, it) for (vii::iterator it = c.begin(); it != c.end(); it++)
#define INF 2000000000

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;

#define MAXVAL 50005

vector<pii> adj_list[MAXVAL];
int main() {
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	int n_nodes, n_arcs;
	scanf("%d%d", &n_nodes, &n_arcs);
	REP(i, 0, n_arcs) {
		int node1, node2, dist_n1_n2;
		scanf("%d%d%d", &node1, &node2, &dist_n1_n2);
		adj_list[node1].push_back(pii(node2, dist_n1_n2));
	}

	int source = 1;
	vector<int> dist_to(n_nodes+1, INF);
	dist_to[source] = 0;
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push(pii(0, source));
	while (!pq.empty()) {
		pii top = pq.top(); pq.pop();
		int dist_to_u = top.first;
		int u = top.second;
		if (dist_to_u == dist_to[u]) {
			TRvii(adj_list[u], i) {
				int v = i->first;
				int dist_u_v = i->second;
				if (dist_to_u + dist_u_v < dist_to[v]) {
					dist_to[v] = dist_to_u + dist_u_v;
					pq.push(pii(dist_to[v], v));
				}
			}
		}
	}
	REP(i, 2, n_nodes+1) {
		if (dist_to[i] == INF) dist_to[i] = 0;
		printf("%d\n", dist_to[i]);
	}
	return 0;
}