#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define infinit 1<<30
#define maxn 50005
struct graf
	{	int nod,cost;
		graf *next;	};
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;
		graf *r;
		scanf("%d%d",&n,&m);
		for(;m;m--)
		{	scanf("%d%d%d",&x,&y,&c);
			r=(graf*)malloc(sizeof(graf));
			r->nod=y; r->cost=c; r->next=a[x];
			a[x]=r;
		}
	}
	
	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(y=a[x];y;y=y->next)
			{
				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;
}