#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n, m, x, y,cost;
vector<pair<int,int>>v[50005];
vector<int>dist(50005, 1000000);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q;
void read() {
	f >> n >> m;
	for (int i = 1; i <= m; i++)
		f >> x >> y>>cost, v[x].push_back(make_pair(y,cost));
q.push(make_pair(0, 1));
dist[1] = 0;}
void solve() {
	while (!q.empty())
	{
		auto x = q.top();
		q.pop();
		int nod = x.second;
		
		for (int i = 0; i < v[nod].size(); i++)
		{
			int vecin = v[nod][i].first;
			int cost = v[nod][i].second;
			if (dist[vecin] > dist[nod] + cost)
				dist[vecin] = dist[nod] + cost;
			q.push(make_pair(dist[vecin], vecin));
		}
		
	}

}
void print() {
	for (int i = 2; i <= n; i++)
		g << dist[i] << " ";



}

int main() {

	read();
	solve();
	print();


}