#include<stdio.h>

const int inf=100000000;
int n,m,d[50001],h[50001],poz[50001],k;
struct nod { int v,c;
             nod * next;
		   } *v[50001];

void citire()
{   int i,x,y,c; 
    nod *p;
	freopen("dijkstra.in","r",stdin);
    scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{   scanf("%d%d%d",&x,&y,&c);
	    p=new nod;
		p->v=y;
		p->c=c;
		p->next=v[x];
		v[x]=p;
	}
	fclose(stdin);
}

void swap(int x,int y)
{   int t=h[x];
    h[x]=h[y];
	h[y]=t;
}

void upheap(int x)
{   int t;
    while(x>1)
	{	t=x>>1;
	    if(d[h[t]]>d[h[x]])
		{   poz[h[x]]=t;
		    poz[h[t]]=x;
			swap(t,x);
			x=t;
		}
		else x=1;
	}
}

void downheap(int x)
{   int f;
    while(x<=k)
	{   f=x;
	    if((x<<1)<=k)
		{   f=x<<1;
		    if(f+1<=k)
				if(d[h[f+1]]<d[h[f]])
					f++;
		}
		else return;
		if(d[h[x]]>d[h[f]])
		{   poz[h[x]]=f;
			poz[h[f]]=x;
			swap(x,f);
			x=f;
		}
		else return ;
	}
}

void dijkstra_heap()
{   int i;
    for(i=2;i<=n;i++)
	{	d[i]=inf;
		poz[i]=-1;
	}
	h[++k]=1;
	while(k)
	{   int min=h[1];
		swap(1,k);
		poz[h[1]]=1;
		--k;
		downheap(1);
		nod *p=v[min];
		while(p!=NULL)
		{   if(d[p->v]>d[min]+p->c)
			{  d[p->v]=d[min]+p->c;
				if(poz[p->v]!=-1)
					upheap(poz[p->v]);
				else 
				{   h[++k]=p->v;
					poz[h[k]]=k;
					upheap(k);
				}
			}
			p=p->next;
		}
	}
}

int main()
{   freopen("dijkstra.out","w",stdout);
    citire();
	dijkstra_heap();
	for(int i=2;i<=n;i++)
		if(d[i]==inf) printf("0 ");
	       else printf("%d ",d[i]);
	fclose(stdout);
	return 0;	
}