#include <stdio.h>
#include <vector>
#define NMAX 50023
#define inf 2000000023
FILE *fin, *fout;
int n, m, x, arb[2*NMAX+1], dij[NMAX], ans[NMAX], p = 1, viz[NMAX], sizen;
int min(int a, int b)
{
	return (a<b)?a:b;
}
struct arc
{
	int vec;
	int cost;
} temp;
std::vector<arc> adj[NMAX];
void pun(int st, int dr, int pos, int nod)
{
	if(st == dr)
	{
		arb[nod] = pos;
		return;
	}
	int mij = (st+dr)/2;
	if(pos <= mij) pun(st, mij, pos, 2*nod);
	else pun(mij+1, dr, pos, 2*nod+1);
	arb[nod] = (dij[arb[2*nod]] < dij[arb[2*nod+1]])?arb[2*nod]:arb[2*nod+1];
	return;
}
int main()
{
	fin = freopen("dijkstra.in", "r", stdin);
	fout = freopen("dijkstra.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 0; i< m; i++)
	{
		scanf("%d%d%d", &x, &temp.vec, &temp.cost);
		adj[x].push_back(temp);
	}
	for(int i = 1; i<= n; i++) dij[i] = inf;
	viz[1] = 1;
	dij[1] = 0;
	for(int u = 0;u<= n;u++)
	{
		sizen = adj[p].size();
		for(int i = 0; i< sizen; i++)
		{
			dij[adj[p][i].vec] = min(dij[adj[p][i].vec], dij[p] + adj[p][i].cost);
			pun(1, n, adj[p][i].vec, 1);
		}
		ans[p] = dij[p];
		dij[p] = inf;
		pun(1, n, p, 1);
		p = arb[1];
	}
	for(int i = 2; i<= n; i++) printf("%d ", ans[i]);printf("\n");
	fclose(fin);
	fclose(fout);
	return 0;
}