#include <fstream>
#include <vector>
#include <queue>
using namespace std;
string file = "dijkstra";
ifstream cin(file + ".in");
ofstream cout(file + ".out");
struct graf {
	int nod, cost;

	bool operator < (const graf& y) const
	{
		return cost > y.cost;
	}
};
struct ura
{
	int nod, cost;
};
vector <ura> L[50001];


vector <int> d(50001,1000000000);


void bfs()
{
	priority_queue <graf> Q;
	d[1] = 0;
	Q.push({ 1,0 });
	while (!Q.empty())
	{
		const int x = Q.top().nod;
		for (ura y : L[x])
		{
			if (d[y.nod] > d[x] + y.cost)
			{
				d[y.nod] = d[x] + y.cost;
				Q.push ({ y.nod,d[y.nod] });
			}
		}
		Q.pop();
	}
}
int main() {
	int n, x, y, z, m;
	cin >> n >> m;
	while (m--)
	{
		cin >> x >> y >> z;
		L[x].push_back({ y,z });
	}
	bfs();
	for (int i = 2; i <= n; i++)
		cout << (d[i] == 1000000000 ? 0 : d[i]) << ' ';
}