#include <fstream>
#define nm 12010
#define inf 1<<30

using namespace std;
ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

int n, m, b[nm];
int a[nm][nm];

void dijkstra(int nod)
{
	int st[nm], p = 0, u = 0, viz[nm];
	for(int i = 1; i <= n; i ++)
	{
		b[i] = inf;
		viz[i] = 0;
	}
	b[nod] = 0;
	viz[nod] = 1;
	st[p] = nod;
	while(p <= u)
	{
		nod = st[p++];
		for(int i = 1; i <= n; i ++)
			if(a[nod][i])
			{
				if(b[nod] + a[nod][i] < b[i])
					b[i] = b[nod] + a[nod][i];
				if(!viz[i])
				{
					viz[i] = 1;
					st[++u] = i;
				}
			}
	}
	for(int i = 2; i <= n; i ++)
		g << b[i] << ' ';
}
int main()
{
	f >> n >> m;
	int x, y, c;
	for(int i = 0; i < m; i ++)
	{
		f >> x >> y >> c;
		a[x][y] = c;
	}
	dijkstra(1);
}