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

int arb[N_MAX*2+1], len, best[N_MAX];
int list[5*N_MAX][3], start[N_MAX], stop[N_MAX], pozitie=0;

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

void add(int a, int b, int c)
{
	++pozitie;
	list[pozitie][0]=b;
	list[pozitie][1]=c;
	list[pozitie][2]=0; //NULL
	if (stop[a]==0)
	{
		start[a]=stop[a]=pozitie;
	}
	else
	{
		list[stop[a]][2]=pozitie;
		stop[a]=pozitie;
	}
	
}
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, 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+list[p][1] < arb[poz+list[p][0]])&&(best[list[p][0]]==INF))
			{
				update(poz+list[p][0], min+list[p][1]);
			}
			p=list[p][2];
		}
	}
	for (i=2; i<=n; i++)
	{
		printf("%d ", best[i]!=INF?best[i]:0);
	}
	fclose(stdout);
	return 0;
}