#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define infinit 1<<30
#define maxn 50005
struct graf
	{	int nod,cost;	};
graf * a[maxn];
int gd[maxn], d[maxn], in_q[maxn];
int *q;
int n;

	void citire(void)
	{	freopen("dijkstra.in","r",stdin);
		int m,x,y,c;
		scanf("%d%d",&n,&m);
		for(;m;m--)
		{	scanf("%d%d%d",&x,&y,&c);
			a[x]=(graf*)realloc(a[x], (gd[x]+1)*sizeof(graf));
			a[x][gd[x]].nod=y; a[x][gd[x]].cost=c;
			gd[x]++;
		}
	}
	
	void bellmanford(void)
	{	int nr=0,i,k,x;
		graf y;
		for(k=2;k<=n;k++) d[k]=infinit;
		q=(int*)realloc(q,(nr+1)*sizeof(int));
		q[nr++]=1; in_q[1]=1; d[1]=0;
		for(i=0; i<nr; i++)
		{	x=q[i]; in_q[x]=0;
			for(k=0;k<gd[x];k++)
			{	y=a[x][k];
				if(d[y.nod]>d[x]+y.cost)
				{	d[y.nod]=d[x]+y.cost;
					if(!in_q[y.nod])
					{	in_q[y.nod]=1;
						q=(int*)realloc(q,(nr+1)*sizeof(int));
						q[nr++]=y.nod;
					}
				}
			}
		}
	}
	
	void scrie(void)
	{	freopen("dijkstra.out","w",stdout);
		for(int i=2;i<=n;i++) printf("%d ",d[i]==infinit?0:d[i]);
	}
	
int main(void)
{	citire();
	bellmanford();
	scrie();
	return 0;
}