#include<stdio.h>
#define max 50010
long d[max], vz[max], n, m;
struct elem
{       long v, c;
	elem *urm;
}	*a[max], *q;
FILE *f, *g;

void read()
{       long i, x, y, cs;
	f=fopen("dijkstra.in", "r");
	fscanf(f, "%ld%ld", &n, &m);
	for(i=0; i<m; i++)
	{	fscanf(f, "%ld%ld%ld", &x, &y, &cs);
		q=new elem;
		q->c=cs; q->v=y;
		q->urm=a[x];
		a[x]=q;
	}
	fclose(f);
}

void solve()
{       long cd[100000], i, p, u;
  /*	for(i=0; i<12; i++)
		cd[i]=0;*/
	for(i=2; i<=n; i++)
		d[i]=2000000000;
	p=1; u=1;
	cd[p]=1; vz[1]=1;
	while(p<=u)
	{       q=a[cd[p]];
		while(q)
		{    	if(q->c+d[cd[p]]<d[q->v])
			{       d[q->v]=q->c+d[cd[p]];
				if(vz[q->v]==0)
				{	u++;
					cd[u]=q->v;
					vz[q->v]=1;
				}
			}
			q=q->urm;
		}
		vz[cd[p]]=0;
		p++;
	}
	for(i=1; i<=n; i++)
		if(d[i]==2000000000)
			d[i]=0;
}

void write()
{	long i;
	g=fopen("dijkstra.out", "w");
	for(i=2; i<=n; i++)
		fprintf(g, "%ld ", d[i]);
	fprintf(g, "\n");
	fclose(g);
}

int main()
{	read();
	solve();
	write();
	return 0;
}