// Dijkstra cu Arbori de intervale
#include <cstdio>
#include <string>
#define N 50001
#define common \
	int m=(l+r)>>1, L=n<<1, R=L|1
#define oo 0x3f3f3f3f

struct nod { int x, c;nod*n;};

nod *a[N];

int H[(1<<17)+1], poz[(1<<17)+1];
int d[N];

int n, m;

void update(int n, int l, int r, int p, int v)
{
	if(l >= r) {H[n]=v;poz[n]=l; return;}
	
	common;
	
	if(p <= m) update(L, l, m, p, v);
	else       update(R, m+1, r, p, v);
	
	if(H[L] < H[R]) H[n]=H[L], poz[n]=poz[L];
	else H[n]=H[R], poz[n]=poz[R];
}

void dijkstra()
{
	int i;
	
	memset(d, oo, sizeof(d));
	d[1]=0;
	for(i=1; i <= n; ++i) update(1,1, n, i, d[i]);

	int nn=n,u;
	nod *it;
	
	while(nn--)
	{
		u=poz[1];
		
		update(1,1,n, u, oo);
		
		for(it=a[u]; it ; it=it->n)
			if(d[u] + it->c < d[it->x])
			{
				d[it->x]=d[u] + it->c;
				update(1, 1, n, it->x, d[it->x]);
			}
	}
	
	for(i=2; i <= n; ++i) printf("%d ", d[i] == oo ? 0 : d[i]);
}

void read()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d %d\n", &n, &m);
	int p, q, c;
	nod *t;
	while(m--)
	{
		scanf("%d %d %d\n", &p, &q, &c);
		t=new nod;
		t->x=q;
		t->c=c;
		t->n=a[p];
		a[p]=t;
	}
}

int main()
{
	read();
	dijkstra();
	return 0;
}