#include <fstream>
#include <vector>
#include <queue>
#include <functional>
#define MAX 2000000000
using namespace std;

vector <pair <int, int>> adia[50010];
priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> q;
int dist[50010];

void djkst(int n);

int main()
{
	ifstream in("dijkstra.in");
	ofstream out("dijkstra.out");
	int n, m, a, b, c;

	in >> n >> m;

	while (m--) {
		in >> a >> b >> c;
		adia[a].push_back({ b, c });
	}
	djkst(n);

	for (int i = 2; i <= n; i++)
		out << (dist[i] != MAX ? dist[i] : 0) << ' ';

	in.close();
	out.close();
	return 0;
}

void djkst(int n)
{
	for (int i = 2; i <= n; i++)
		dist[i] = MAX;
	q.push({ 0, 1 });

	while (!q.empty()) {
		int nod = q.top().second;
		q.pop();

		for (auto i : adia[nod]) {
			if (dist[i.first] > dist[nod] + i.second) {
				dist[i.first] = dist[nod] + i.second;
				q.push({ dist[i.first], i.first });
			}
		}
	}
}