#include <stdio.h>

struct nod {
	int inf,c;
	nod *next;
};

const int maxn=50001;
const long int INFINIT=250000001;
nod *A[maxn];
int H[maxn],poz[maxn],i,N,M,hp;
long int D[maxn];

void swap(int *a,int *b)
{
	int aux;
	aux=*a;
	*a=*b;
	*b=aux;
}

void upheap(int k)
{
	while(k>1 && D[H[k]]<D[H[k/2]])
	{
		swap(&poz[H[k]],&poz[H[k/2]]);
		swap(&H[k],&H[k/2]);
		k/=2;
	}
}
void downheap(int k)
{
	int son;
	do
	{
		son=0;
		if(2*k<=hp)
		{
			son=2*k;
			if(2*k+1<=hp && D[H[son]]>D[H[2*k+1]])
				son=2*k+1;
			if(D[H[son]]>=D[H[k]]) son=0;
			
		}
		if(son)
		{
			swap(&poz[H[son]],&poz[H[k]]);
			swap(&H[son],&H[k]);
			k=son;
		}
	}
	while(son);
}

void dijk(int s)
{
	nod *x; int min;
	for(i=1;i<=N;i++) D[i]=INFINIT;
	for(i=1;i<=N;i++) poz[i]=0;
	hp=1; H[1]=s; poz[s]=1; D[1]=0;
	while(hp)
	{
		poz[H[hp]]=1;
		min=H[1];
		swap(&H[1],&H[hp]);
		hp--;
		downheap(1);
		x=A[min];
		while(x!=NULL)
		{
			if(D[min]+x->c<D[x->inf])
			{
				D[x->inf]=D[min]+x->c;
				if(poz[x->inf]>0) upheap(poz[x->inf]);
				  else
				  {
					  H[++hp]=x->inf;
					  poz[x->inf]=hp;
					  upheap(hp);
				  }
			}
			x=x->next;
		}
	}
}

int main()
{
	int x,y,z;
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d %d",&N,&M);
	for(i=1;i<=M;i++)
	{
		scanf("%d %d %d",&x,&y,&z);
		nod *q=new nod;
		q->c=z;
		q->inf=y;
		q->next=A[x];
		A[x]=q;
	}
	dijk(1);
	for(i=2;i<=N;i++) 
		if(D[i]==INFINIT) printf("0 ");
	    else printf("%ld ",D[i]);
}