#include<stdio.h>
#include<string.h>
#define N_MAX 65536
#define INF 0x7F7F7F7F

int arb[N_MAX*2+1], len, best[N_MAX];

inline int min(int a, int b)
{
	if (a<=b) return a;
	return b;
}

struct entry
{
	int val, cost;
	entry *adr;
} *start[N_MAX], *stop[N_MAX];

void add(int a, int b, int c)
{
	entry *p;
	p=new entry;
	p->val=b;
	p->cost=c;
	p->adr=NULL;
	if (stop[a]==NULL)
		stop[a]=start[a]=p;
	else
	{
		stop[a]->adr=p;
		stop[a]=stop[a]->adr;
	}
}
void update(int unde, int val)
{
	arb[unde]=val;
	unde/=2;
	
	while (unde>=1)
	{	
		arb[unde]=min(arb[unde*2], arb[unde*2+1]);
		unde/=2;
	}
}
int afla_poz_min()
{
	int p=1;
	while(p<len)
	{
		if(arb[p*2]==arb[p])
			p=p*2;
		else
			p=p*2+1;
	}
	return p;
}

int main()
{
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	
	int n, m, i, a, b, c, poz, st=1, nr=0, unde, min;
	entry	*p;
	scanf("%d %d", &n, &m);
	for (i=1; i<=m; i++)
	{
		scanf("%d %d %d", &a, &b, &c);
		add(a, b, c);
	}
	for(len=1; len<n; len<<=1);
	poz=len-1;//apelam pozitia inc are vrem sa facem update cu poz+i unde i e pozitia pe care vrem updateul
	memset(arb, 0x7f, (N_MAX*2+1)*4);
	
	update(poz+st, 0);
	
	
	for (i=1;i<=n; i++)
	{
		best[i]=INF;
	}
	
	while (nr<n)
	{
		++nr;
		unde=afla_poz_min();
		min=arb[1];
		update(unde, INF);
		
		best[unde-poz]=min;
		p=start[unde-poz];
		while(p)
		{
			if ((min+p->cost < arb[poz+p->val])&&(best[p->val]==INF))
			{
				update(poz+p->val, min+p->cost);
			}
			p=p->adr;
		}
	}
	for (i=2; i<=n; i++)
	{
		printf("%d ", best[i]!=INF?best[i]:0);
	}
	fclose(stdout);
	return 0;
}