#include<stdio.h>
#define Nmax 51100
#define infinit 2000000000
int vec[Nmax],n,nr,ot[Nmax],nrcrt,d[Nmax],m,viz[Nmax];
struct heap
{
	int val,crt;
}h[Nmax];
struct nod
{
	int inf,cost;
	nod *urm;
}*a[Nmax];

void urca(int poz,int n)
{
	heap aj;
	if(poz>1)
		if(h[poz].val<h[poz/2].val)
		{
			aj=h[poz];
			h[poz]=h[poz/2];
			h[poz/2]=aj;
			
			urca(poz/2,n);
		}
}

int min(int poz,int n)
{
	if(2*poz+1<=n)
		if(h[2*poz].val<h[2*poz+1].val)
			return 2*poz;
		else
			return 2*poz+1;
	else
		return 2*poz;
			
}

void coboara(int poz,int n)
{
	int aj;
	heap z;
	if(2*poz<=n)
	{
		aj=min(poz,n);
		if(h[aj].val<h[poz].val)
		{
			z=h[aj];
			h[aj]=h[poz];
			h[poz]=z;

			coboara(aj,n);
		}
	}
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	int x,y,c;
	nod *p;
	scanf("%d %d",&n,&m);
	for(int i=2;i<=n;i++)
		d[i]=infinit;
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d",&x,&y,&c);
		p=new nod;
		p->inf=y;
		p->cost=c;
		p->urm=a[x];
		a[x]=p;
		if(x==1)
		{
			d[y]=c;
			viz[y]=1;
			nr++;
			h[nr].crt=y;
			h[nr].val=d[y];
			urca(nr,nr);
		}
	}
	viz[1]=1;
	int s;
	while(nr>0)
	{
		s=h[1].crt;
		for(p=a[s];p!=NULL;p=p->urm)
			if(d[p->inf]>d[s]+p->cost)
			{
				d[p->inf]=d[s]+p->cost;
				viz[p->inf]=1;
				nr++;
				h[nr].crt=p->inf;
				h[nr].val=d[p->inf];
				urca(nr,nr);
			}
		h[1]=h[nr];
		nr--;
		coboara(1,nr);
	}
	for(int i=2;i<=n;i++)
		if(d[i]==infinit)
			printf("0 ");
		else
			printf("%d ",d[i]);
	return 0;
}