#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#define NMAX 50001

using namespace std;

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

const int INF = 1e9;
struct costs
{	//decl struct
	int nod, cost;

	public:
	costs(int n, int c) {
		nod = n;
		cost = c;
	}
};

auto cmp = [](const costs & left, const costs & right)
{	//cmp function for heap
	if (left.cost == right.cost)
		return left.nod > right.nod;
	return left.cost < right.cost;
};
multiset <costs, decltype(cmp)> h(cmp);				//heap
vector <int> d;										//dist sursa -> nod
vector <bool> viz;									//vizitat
vector <costs> v[NMAX];								//cst de la un nod la altul

int n, m;

int main()
{
	int nod, vec, cst;

	f >> n >> m;
	for (int i = 1; i <= m; ++i) {
		f >> nod >> vec >> cst;
		costs c(vec, cst);

		v[nod].push_back(c);
	}

	viz = vector<bool>(n + 1, false);
	d = vector<int>(n + 1, INF);
	d[1] = 0;
	h.insert(costs(1, 0));

	while (!h.empty()) {
		auto it = h.begin();
		nod = (*it).nod;
		h.erase(it);

		if (!viz[nod]) {
			for (int i = 0; i < v[nod].size(); ++i)
				if (d[nod] + v[nod][i].cost < d[v[nod][i].nod])
				{
					d[v[nod][i].nod] = d[nod] + v[nod][i].cost;
					h.insert(costs(v[nod][i].nod, d[v[nod][i].nod]));
				}
		}
		viz[nod] = true;
	}

	for (int i = 2; i <= n; ++i) {
		if (d[i] == INF) g << 0 << ' ';
		else g << d[i] << ' ';
	}

	return 0;
}