#include<stdio.h>
#define N 5000
int n,m,i,j,x,y,l,d[N],coada[N+N],ic,sf,ap[N],v[N];
struct structura
{
	int a,b,c;
}str[N];
int *a[N],*c[N];
void read()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)
		d[i]=100000;
	for(i=1;i<=m;++i)
	{
		scanf("%d%d%d",&str[i].a,&str[i].b,&str[i].c);
		v[str[i].a]++;
	}
	for(i=1;i<=n;++i)
	{
		a[i]=new int[v[i]+1];
		c[i]=new int[v[i]+1];
		a[i][0]=c[i][0]=0;
	}
	for(i=1;i<=m;++i)
	{
		x=str[i].a;
		y=str[i].b;
		l=str[i].c;
		a[x][++a[x][0]]=y;
		c[x][++c[x][0]]=l;
	}
}
void parcurgere()
{
	int x;
	ic=sf=1;
	coada[ic]=1;
	d[1]=0;
	while(ic<=sf)
	{
		x=coada[ic++];
		ap[x]=0;
		for(i=1;i<=a[x][0];++i)
			if(d[a[x][i]]>c[x][i]+d[x])
			{
				if(!ap[a[x][i]])
				{
					coada[++sf]=a[x][i];
					ap[a[x][i]]=1;
				}
				d[a[x][i]]=c[x][i]+d[x];
			}
		//ic++;
	}
	for(i=2;i<n;++i)
	{
		if(d[i]==100000)
			printf("0 ");
		else
			printf("%d ",d[i]);
	}
	if(d[n]==100000)
		printf("0 ");
	else
		printf("%d\n",d[n]);
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	read();
	parcurgere();
	return 0;
}