// Dijkstra

#include <stdio.h>
#define maxn 50001

struct graf{
	int nod, cost;
	graf *nxt;
} *a[maxn],*q;

int n,m;
int d[maxn]={-1}, dim=0;
int p[maxn]={-1}, h[maxn];

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

void up (int k)
{
	if (k>1) {
	if (d[h[k]]< d[h[k/2]])
	{	swap(k,k/2);
		up(k/2);
	}		 }
}

void down (int k)
{
	int min=k;
	if ( k*2<= dim && d[h[k*2]]<d[h[min]])
		min=k*2;
	if ( k*2+1<= dim && d[h[k*2+1]]<d[h[min]])
		min=k*2+1;
	if (min!=k)
	{	swap(min,k);
		down(min);
	}
}


void dijkstra ( )
{
	h[++dim]=1; //initializez heapul
	p[1]=1;

	while (dim) //cat timp heapul nu e gol
	{
		swap(1,dim); //extrag minimul
		down(1);
		dim--;
		int min=h[1];
		graf *q= a[min];

		while (q)
		{
			if ( d[q->nod]> d[min]+ q->cost  || d[q->nod]==-1)
			{
			   d[q->nod]= d[min]+ q->cost;

			   if(p[q->nod]!= -1)
				  up(p[1]);
			   else
			   {
				   h[++dim]= q->nod;
				   p[h[dim]]=dim;
				   up(dim);
			   }
			}  //end.if
			q=q->nxt;
		}	//end.while
	}	//end.while
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d %d", &n, &m);
	int i,x,y,c;
	for(i= 1; i<= m; ++i)
	{
		scanf("%d %d %d", &x, &y, &c);
		q= new graf;
		q-> nxt= a[x];
		q-> nod= y;
		q-> cost= c;
		a[x]= q;
	}

	d[1]=0;
	dijkstra ();

	for(i=2; i<=n; ++i)
    if(d[i]!=-1)
		printf("%d ",d[i]);
	else
	    printf("0 ");

	fclose(stdout);
	return 0;
}