#include <fstream>
#include <queue>
#include <vector>
#include <climits>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int nMax = 50000 + 1;
const int oo = INT_MAX;
struct edges {
	int nod, cost;
};
int n;
vector<edges>G[nMax];
vector<int>dis(nMax, 0);
vector<bool>inQueue(nMax, false);
void dijkstra(int start) {
	using P = pair<int, int>;
	priority_queue<P, vector<P>, greater<P>>Pq;
	for (int i = 1; i <= n; ++i)
		dis[i] = oo;
	dis[start] = 0;
	inQueue[start] = true;
	Pq.push({ 0,start });
	while (!Pq.empty()) {
		auto i = Pq.top();
		int nodCurent = i.second;
		Pq.pop();
		inQueue[nodCurent] = false;
		for (auto j : G[nodCurent]) {
			int vertex = j.nod;
			int price = j.cost;
			if (dis[vertex] >= dis[nodCurent] + price) {
				dis[vertex] = dis[nodCurent] + price;
				if (inQueue[vertex] == false) {
					Pq.push({ dis[vertex],vertex });
					inQueue[vertex] = true;
				}
			}
		}
	}
}
int main() {
	int m;
	f >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int x, y, z;
		f >> x >> y >> z;
		G[x].push_back({ y,z });
	}
	dijkstra(1);
	for (int i = 2; i <= n; ++i)
		if (dis[i] == oo)
			g << 0 << ' ';
		else
			g << dis[i] << ' ';
	return 0;
}