#ifdef __INFOARENA_PROJ
#include "infoarena.h"
#endif

#include <fstream>
#include <vector>
#include <queue>
#include <functional>
#include <utility>
#include <cstring>

#ifdef __INFOARENA_PROJ
namespace dijkstra {
#endif

const unsigned int maxN = 50000, maxL = 1000;
typedef std::pair<unsigned, unsigned> muchie;
std::vector<muchie> G[maxN + 1];
struct greater
{
	bool operator() (const muchie& m1, const muchie& m2) { return m1.second > m2.second; }
};

int main()
{
	std::ifstream in("dijkstra.in");
	std::ofstream out("dijkstra.out");
	unsigned N, M, x, y, c;
	in >> N >> M;
	for (unsigned i = 0; i < M; ++i)
	{
		in >> x >> y >> c;
		G[x].push_back(muchie(y, c));
	}

	unsigned D[maxN + 1];
	bool viz[maxN + 1];
	memset(D, 0x77, sizeof D);
	memset(viz, 0, sizeof viz);
	D[1] = 0;
	viz[1] = true;

	std::priority_queue<muchie, std::vector<muchie>, greater> q;
	q.push(muchie(1, 0));
	while (!q.empty())
	{
		unsigned nod = q.top().first;
		q.pop();
		std::vector<std::pair<unsigned, unsigned>>::const_iterator it;
		for (it = G[nod].cbegin(); it != G[nod].cend(); ++it)
		{
			unsigned vec = (*it).first, cost = (*it).second;
			if (viz[vec])
				continue;

			if (D[nod] + cost < D[vec])
			{
				D[vec] = D[nod] + cost;
				q.push(muchie(vec, D[vec]));
			}
		}
		viz[nod] = true;
	}
	
	for (unsigned i = 2; i <= N; ++i)
	{
		if (D[i] == 0x77777777)
			D[i] = 0;
		out << D[i] << ' ';
	}
	out << '\n';
	return 0;
}


#ifdef __INFOARENA_PROJ
}
#endif