#include<cstdio>
#include<iostream>
using namespace std;
long n,m;
struct muchie
{
	long x,y,c;
}a[25000];
long d[50001];
int main()
{
	freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);

	long i;
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].c);
		if(a[i].x==1)
			d[a[i].y]=a[i].c;
	}
	for(i=1;i<=n;i++)
		if(d[i]==0)
			d[i]=250010;
		int gata=0;
	while(!gata)
	{
		gata=1;
		for(i=1;i<=m;i++)
			if(d[a[i].y]>d[a[i].x]+a[i].c)
			{
				gata=0;
				d[a[i].y]=d[a[i].x]+a[i].c;
			}
	}
	for(i=2;i<=n;i++)
		if(d[i]>=32000)
			printf("0 ");
		else
			printf("%d ",d[i]);
		return 0;}