#include<stdio.h>
#define N 50001
#define M 250001
#define oo 2000000
int x[M],y[M],n,m,d[M],pred[N],*a[N],*a1[N];
bool sel[N];
struct consturi{int x,y,z;}c[N];
void citire()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1; i<=m; ++i)
	{
		scanf("%d%d%d",&c[i].x,&c[i].y,&c[i].z);
		++d[c[i].x];
	}
	for (int i=1; i<=n; ++i)
	{
		a[i]=new int [1+d[i]];
		a[i][0]=0;
		a1[i]=new int [1+d[i]];
		a1[i][0]=0;
	}
	for (int i=1; i<=m; ++i)
	{
		a[c[i].x][++a[c[i].x][0]]=c[i].y;
		a1[c[i].x][++a1[c[i].x][0]]=c[i].z;
	}
}
int min()
{
	int min=oo,pmin;
	for (int i=1; i<=n; ++i)
	{
		if (!sel[i] && d[i]<min)
		{
			min=d[i];
			pmin=i;
		}
	}
	return pmin;
}
void update(int x)
{
	for (int i=1; i<=a[x][0]; ++i)
	{
		int y=a[x][i],c=a1[x][i];
		if (d[x]+c<d[y])
		{
			d[y]=d[x]+c;
			pred[y]=x;
		}
	}
}
void dijkstra(int x0)
{
	for (int i=1; i<=n; ++i)
	{
		d[i]=oo;
		pred[i]=0;
		sel[i]=false;
	}
	d[x0]=0;
	for (int i=1; i<=n-1; ++i)
	{
		int x=min();
		sel[x]=true;
		update(x);
	}
}
void afis()
{
	for (int i=2; i<=n; ++i)
		if (d[i]!=oo)
			printf("%d ",d[i]);
		else
			printf("0 ");
}
int main()
{
	citire();
	dijkstra(1);
	afis();
	return 0;
}