#include <iostream>
#include <fstream>
#define inf INT_MAX
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct nod
{
	int info, cost;
	nod *urm;
}*a[100005];
int d[100005], used[100005], c[300005];
void adaugare(int x, int cos, nod *&prim)
{
	nod *p = new nod;
	p->info = x;
	p->cost = cos;
	p->urm = prim;
	prim = p;
}
void dijkstra(int k)
{
	d[k] = 0;
	used[k] = 1;
	int p, u;
	p = u = 1;
	c[p] = k;
	while (p <= u)
	{
		int x = c[p++];
		used[x] = 0;
		for (nod *p = a[x]; p; p = p->urm)
		{
			if (d[p->info] > d[x] + p->cost)
			{

				d[p->info] = d[x] + p->cost;
				if (!used[p->info])c[++u] = p->info, used[p->info] = 1;
			}
		}
	}
}
int n, m, v;
int main()
{
	fin >> n >> m;
	while (m)
	{
		int x, y, cost;
		fin >> x >> y >> cost;
		adaugare(y, cost, a[x]);

		--m;
	}
	for (int i = 2; i <= n; ++i)d[i] = inf;
	dijkstra(1);
	for (int i = 2; i <= n; ++i, fout << " ")if (d[i] == inf)fout << 0; else fout << d[i] << " ";
	return 0;
}