#define DM 50001
#define inf 0x3f3f3f3f
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

ifstream fi ("dijkstra.in");
ofstream fo ("dijkstra.out");

struct str {
	int nod, cost;
	bool operator < (const str &other) const {
		return cost > other.cost;
	}
};

int n, m, a, b, c, dist[DM];
priority_queue <str> pq;
vector <str> v[DM];


int main()
{
	fi >> n >> m;
	for (int i = 1; i <= m; ++i)
	{
		fi >> a >> b >> c;
		v[a].push_back({b, c});
	}
	for (int i = 2; i <= n; ++i)
		dist[i] = inf;
	pq.push({1, 0});
	while (!pq.empty())
	{
		a = pq.top().nod, b = pq.top().cost;
		pq.pop();
		if (dist[a] > b)
			continue;
		for (int i = 0; i < v[a].size(); ++i)
		{
			if (dist[v[a][i].nod] > b + v[a][i].cost)
			{
				dist[v[a][i].nod] = b + v[a][i].cost;
				pq.push({v[a][i].nod, dist[v[a][i].nod]});
			}
		}
	}
	for (int i = 2; i <= n; ++i)
		fo << (dist[i] != inf ? dist[i]:0) << ' ';
	return 0;
}