#include <fstream>
#include <vector>
#include <deque>
#include <queue>
#include <iostream>

using namespace std;

const int inf = 1e8;
const int NMAX = 5e4 + 10;
vector < pair <int, int> > v[NMAX];
bool viz[NMAX];

int main() {	
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");

	int n, m;
	f >> n >> m;
	while (m--) {
		//cout << m << "\n";
		int x, y, z;
		f >> x >> y >> z;
		//cout << x << " " << y << " " << z << "\n";
		v[x].push_back({ y,z });
	}

	priority_queue < pair < int, int > > q;
	vector < int > dist(n + 1, inf);
	dist[1] = 0;
	q.push({ 0, 1 });
	while (!q.empty()) {
		int node = q.top().second;
		q.pop();

		if (viz[node]) 
			continue;
		viz[node] = 1;

		for (auto it : v[node]) {
			if (dist[it.first] > dist[node] + it.second) {
				dist[it.first] = dist[node] + it.second;
				q.push({ -dist[it.first], it.first });
			}
		}
	}

	for (int i = 2; i <= n; i++)
		if (dist[i] == inf)
			g << 0 << " ";
		else
			g << dist[i] << " ";

	return 0;
}