#include <cstdio>


struct arc
{
	int x;
	int y;
	int c;
}v[250001];
int n,m,i,j,X,Y,cost;
int inf=10000,dmin,vmin;
int p[50001],d[50001],s[50001];

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d %d",&n,&m);
		
	for(i=1;i<=m;i++)
	{
		scanf("%d %d %d",&X,&Y,&cost);
		v[i].x=X;
		v[i].y=Y;
		v[i].c=cost;
	}
	
	for(i=1;i<=n;i++)
	{
		p[i]=0;
		d[i]=inf;
		s[i]=0;
	}
	s[1]=1;
	for(i=1;i<=m;i++)
	{
		if(v[i].x==1)
		{
			d[v[i].y]=v[i].c;
			p[v[i].y]=1;
		}
	}
			
		
	
	for(j=1;j<=n;j++)
	{
		dmin=inf;
		vmin=0;
		for(i=1;i<=n;i++)
			if(s[i]==0 && d[i]<dmin)
			{
				dmin=d[i];
				vmin=i;
			}
		if(vmin!=0)
		{
			s[vmin]=1;
			for(i=1;i<=m;i++)
			{
				if(v[i].x==vmin)
					if(d[v[i].y]>d[vmin]+v[i].c)
					{
						d[v[i].y]=d[vmin]+v[i].c;
						p[i]=vmin;
					}
			}
		}
	}
	for(i=2;i<=n;i++)
		printf("%d ",d[i]);
	printf("\n");

	return 0;
}