#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define oo 2e9

using namespace std;

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

struct NOD
{
	int nod;
	int cost;
};

vector<NOD>G[50001];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>>pq;
int d[50001];
int n, m;


void citire()
{
	in >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y, cost;
		in >> x >> y >> cost;
		G[x].push_back({ y,cost });
	}
}

void dijkstra()
{
	for (int i = 1; i <= n; i++)
		d[i] = oo;
	d[1] = 0;
	pq.push({ 0,1 });
	while (!pq.empty())
	{
		int nod_curent, cost_curent;
		cost_curent = pq.top().first;
		nod_curent = pq.top().second;
		pq.pop();
		if (cost_curent > d[nod_curent])
			continue;
		for (auto it : G[nod_curent])
		{
			if (d[it.nod] > it.cost + cost_curent)
			{
				d[it.nod] = it.cost + cost_curent;
				pq.push({ d[it.nod], it.nod });
			}
		}
	}
}

int main()
{
	citire();
	dijkstra();
	for (int i = 2; i <= n; i++)
		if (d[i] == oo)
			out << "0 ";
		else out << d[i] << " ";
	return 0;
}