#include<stdio.h>
#include<string.h>
#define maxn 50001
#define oo 0x3f
FILE *f=fopen("dijkstra.in","r"), *g=fopen("dijkstra.out","w");

struct lista{ int nod,c; 
			lista *urm;} *G[maxn];
int t[maxn],h[maxn],poz[maxn],D[maxn];
int n,m,x,y,cost,i,nn,nod;
void swap(int i, int j)
{
	int aux;
	aux=h[i]; h[i]=h[j]; h[j]=aux;
	
	poz[h[i]]=i;
	poz[h[j]]=j;
}

void heapdown(int r, int k)
{
	int i,st,dr;
	if(2*r+1<=k)
	{
		st=h[2*r+1];
		if(2*r+2<=k) dr=h[2*r+2];
		else dr=st-1;
		if(st>dr) i=2*r+1;
		else i=2*r+2;
	}
	
	if(D[h[i]]<D[h[r]])
	{
		swap(r,i);
		heapdown(i,k);
	}
}

void heapup(int k)
{
	if(k<=0) return;
	int t=k/2;
	if(D[h[t]]>D[h[k]])
	{
		swap(k,t);
		heapup(t);
	}
}

void build(int k)
{
	int i;
	for(i=2;i<=k;i++) heapup(i);
}
/*void pop()
{
	swap(1,nn);
	nod=h[nn];
	poz[h[nn]]=0;
	nn--;
	heapdown(1,nn);

}	*/
	
void dijkstra(int s)
{
	int i;
	lista *p;
	memset(t,0,sizeof(t));
	memset(D,oo,sizeof(D));
	
	for(i=1;i<=n;i++)
	{
		h[i]=i;
		poz[i]=i;
	}
	
	D[s]=0;
	build(n);
	nn=n;
	while(nn>=0)
	{
		nod=h[1];
		swap(1,nn);
		poz[h[nn]]=0;
		nn--;
		heapdown(1,nn);
		
		
		for(p=G[nod]; p!=NULL; p=p->urm)
		{
			if(D[p->nod]>D[nod]+p->c)
			{
				D[p->nod]=D[nod]+p->c;
				t[p->nod]=nod;
				heapup(poz[p->nod]);
			}
		}
	}
}

int main()
{
	
	lista *q;
	fscanf(f,"%d %d",&n,&m);
	for(i=1;i<=m;i++)
	{
		fscanf(f,"%d %d %d",&x,&y,&cost);
		
		q= new lista;
		q->nod=y;
		q->c=cost;
		q->urm=G[x];
		G[x]=q;
	}
	

	dijkstra(1);
	
	for(i=2;i<=n;i++)
			fprintf(g,"%d ", D[i]==oo ? 0 : D[i]);
	fprintf(g,"\n");
		
	
	fclose(f);
	fclose(g);
	return 0;
}