#include<stdio.h>
#define N 50001
#define M 250001
#define INF 1000000
int n,m,d[N],use[N],niv[N],c[N*10];
struct vec{
	int x,y,c;
}v[M];
struct col{
	int x,c;
}*a[N];
void read()
{
	int i;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].c);
		niv[v[i].x]++;
		//niv[v[i].y]++;
	}
	for(i=1;i<=n;i++)
	{
		a[i]=new col[niv[i]+1];
		a[i][0].x=a[i][0].c=0;
	}
	for(i=1;i<=m;i++)
	{
		a[v[i].x][++a[v[i].x][0].x].x=v[i].y;
		//a[v[i].y][++a[v[i].y][0].x].x=v[i].x;
		a[v[i].x][++a[v[i].x][0].c].c=v[i].c;
		//a[v[i].y][++a[v[i].y][0].c].c=v[i].c;
	}
	/*for(i=1;i<=n;i++)
		for(j=1;j<=a[i][0].x;j++)
			printf("%d %d %d\n",i,a[i][j].x,a[i][j].c);*/
	for(i=1;i<=n;i++)
		d[i]=INF;
	/*for(i=1;i<=a[1][0].x;i++)
		d[a[1][i].x]=a[1][i].c;*/
	d[1]=0;
}
void solve()
{
	int i,ic,sf,nod;
	c[1]=1;
	use[1]=1;
	for(ic=sf=1;ic<=sf;ic++)
	{
		nod=c[ic];
		for(i=1;i<=a[nod][0].x;i++)
			if(!use[a[nod][i].x]&&d[a[nod][i].x]>d[nod]+a[nod][i].c)
			{
				d[a[nod][i].x]=d[nod]+a[nod][i].c;
				c[++sf]=a[nod][i].x;
				use[a[nod][i].x]=1;
			}
	}
	for(i=2;i<n;i++)
		printf("%d ",d[i]==INF?0:d[i]);
	printf("%d\n",d[n]);
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	read();
	solve();
	return 0;
}