#include <stdio.h>
#define inf 1 << 30
#define maxn 50001
FILE *f,*g;
struct graf{
	int nod,cost;
	graf *urm;
};
int n,m;
graf *a[maxn];
int d[maxn],uz[maxn];

void add(int unde,int ce,int cost){
	graf *q=new graf;
	q->nod=ce;
	q->cost=cost;
	q->urm=a[unde];
	a[unde]=q;
}

void cit(){
	int i;
	int x,y,z;
	f=fopen("dijkstra.in","r");
	fscanf(f,"%d %d",&n,&m);
	for (i=1;i<=m;i++)
	{
		fscanf(f,"%d %d %d ",&x,&y,&z);
		add(x,y,z);
	}
}

void dijkstra(){
	int i,qmin,pmin=0,j;
	int min;
	for (i=2;i<=n;i++)
		d[i]=inf;
	for (i=1;i<=n;i++)
	{
		min=inf;
		for (j=1;j<=n;j++)
			if (d[j]<min&&!uz[j])
				min=d[j],pmin=j;
		uz[pmin]=1;
		graf *t=a[pmin];
		while (t)
		{
			if (d[t->nod]>d[pmin]+t->cost)
				d[t->nod]=d[pmin]+t->cost;
			t=t->urm;
		}
	}
}

int main(){
	cit();
	dijkstra();
	g=fopen("dijkstra.out","w");
	for (int i=2;i<=n;i++)
		fprintf(g,"%d ",d[i]==inf?0:d[i]);
	fprintf(g,"\n");
	fclose(g);
	return 0;
}