#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct edge {
	int to, cost;
};

struct dijkstraCandidate {
	int cost, node;

	bool operator > (const dijkstraCandidate& other) const {
		return cost > other.cost || (cost == other.cost && node > other.node);
	}
};

const int NMAX = 50505;
const int INF = 0x3f3f3f3f;

int N, M;
vector<edge> G[NMAX];

void read() {
	scanf("%d%d", &N, &M);
	int x, y, cost;
	for (int edgeIdx = 0; edgeIdx < M; edgeIdx++) {
		scanf("%d%d%d", &x, &y, &cost);
		G[x].push_back({y, cost});
	}
}

void solve() {
	vector<int> D(N + 1, INF);
	priority_queue<dijkstraCandidate, vector<dijkstraCandidate>, greater<dijkstraCandidate>> Q;

	D[1] = 0;
	Q.push({0, 1});
	while (!Q.empty()) {
		int bestNode = Q.top().node;
		int bestNodeCost = Q.top().cost;
		Q.pop();

		if (D[bestNode] < bestNodeCost) {
			// multiple estimates for the same node. this is an older one
			continue ;
		}

		for (auto& outgoingEdge : G[bestNode]) {
			if (D[outgoingEdge.to] > D[bestNode] + outgoingEdge.cost) {
				D[outgoingEdge.to] = D[bestNode] + outgoingEdge.cost;
				Q.push({D[outgoingEdge.to], outgoingEdge.to});
			}
		}
	}

	for (int node = 2; node <= N; node++) {
		if (D[node] == INF) {
			printf("0 ");
		} else {
			printf("%d ", D[node]);
		}
	}
	printf("\n");
}

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

	read();
	solve();
	return 0;
}