#include<cstdio>
struct gr{
	int nr;
	int vec[5000];
	int c[5000];
}a[50000];
int t[50000],d[50000],n,m,k,i,j,viz[50000],x,y,c,ok,min;


void citire()
{
	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,&c);
		a[x].nr++;
		a[x].vec[a[x].nr]=y;
		a[x].c[a[x].nr]=c;
	}
	for(i=1;i<=n;i++){
		t[i]=1;
		d[i]=9999;
	}
	for(i=1;i<=a[1].nr;i++)d[a[1].vec[i]]=a[1].c[i];
	t[1]=0;ok=1;k=1;
}

int main()
{
	citire();
	while (ok==1){
		min=9999;viz[k]=1;
		
		for(i=1;i<=n;i++)
		if(d[i]<min && viz[i]==0){
			min=d[i];
			k=i;
		}
		
		if(min!=9999){
			for(i=1;i<=a[k].nr;i++)
				if(d[a[k].vec[i]]>min+a[k].c[i]){
					d[a[k].vec[i]]=min+a[k].c[i];
					t[a[k].vec[i]]=k;
		}
		}
		else ok=0;
	}
	for(i=2;i<=n;i++)
		if (d[i]==9999)printf("0 ");
	else printf("%d ",d[i]);
	return 0;
}