#include<fstream>
#define INF 1000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int a[101][101], d[101], incoada[101], c[101], t[101];
int main()
{
	int n, m, i, j, k, x, y, v, p, u, o;
	f >> n >> m;
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			a[i][j] = INF;
	for (i = 1; i <= m; i++)
	{
		f >> x >> y >> v;
		a[x][y] = v;
	}
	for (i = 1; i <= n; i++)
		d[i] = INF;
	o = 1;
	d[o] = 0;
	p = u = 1;
	c[p] = o;
	incoada[o] = 1;
	while (p <= u)
	{
		x = c[p];
		p++;
		incoada[x] = 0;
		for (i = 1; i <= n; i++)
		{
			if (a[x][i]<INF && d[x] + a[x][i]<d[i])
			{
				d[i] = d[x] + a[x][i];
				t[i] = x;
				if (incoada[i] == 0)
				{
					c[++u] = i;
					incoada[i] = 1;
				}
			}

		}
	}
	for (i = 2; i <= n; i++)
		g << d[i] << " ";
	return 0;
}