#include<cstdio>
#define DN 50005
int n, m, s[DN], d[DN], p[DN];
FILE *f=fopen("dijkstra.in", "r");
FILE *g=fopen("dijkstra.out", "w");
struct graf
{
	int nod, c;
	graf *urm;
}*a[DN];
void NO_TO_ACTA()
{
	for(int i=1; i<=m; ++i)
	{
		int x, y, c;
		fscanf(f, "%d%d%d", &x, &y, &c);
		graf *q = new graf;
		q->nod=y;
		q->c=c;
		q->urm=a[x];
		a[x]=q;
	}
}
/**
void afis()
{
	for(int i=1; i<=n; i++)
	{
		graf *q=a[i];
		fprintf(g, "%d: ", i);
		while(q!=NULL)
		{
			fprintf(g, "%d ", q->nod);
			q=q->urm;
		}
		fprintf(g, "\n");
	}
}**/
int main()
{
	fscanf(f, "%d%d", &n, &m);
	NO_TO_ACTA();
	//afis();
	bool ok=1; int i=1;
	while(ok)
	{
		graf *q;
		q=a[i]; i++; ok=0;
		while(q!=NULL)
		{
			if(d[q->nod]>d[i]+q->c)
			{
				d[q->nod]=d[i]+q->c; 
				ok=1;
			}
			q=q->urm;
		}
	}
	for(int i=2;i<=n;i++)
		if(d[i]!=DN)
			fprintf(g, "%d ", d[i]);
		else
			fprintf(g, "0 ");
}