#include<stdio.h>
#define N 50010
#define M 250010
int heap[N],poz[N],dist[N],he=1,*d[N],*c[N],n,m,aux; 
//he=heap entries
//d[] = destinatie c[] = cost pana la d[]

struct muchie{ int s,d,c; } drum[M]; //tin muchiile dupa ce le citesc

void replace(int p, int q)
{
	aux=poz[heap[p]];
	poz[heap[p]]=poz[heap[q]];
	poz[heap[q]]=aux;
	aux=heap[p];
	heap[p]=heap[q];
	heap[q]=aux;
}

void up(int x)
{
	while(dist[heap[x]]<dist[heap[x/2]])
	{
		replace(x,x/2);
		x/=2;
	}
}

void down(int x)
{
	int son;
	while((2*x<he)&&((dist[heap[x]]>dist[heap[2*x]])||(dist[heap[x]]>dist[heap[2*x+1]]))){
		if(dist[heap[2*x+1]]>dist[heap[2*x]]) son=2*x;
		else son=2*x+1;
		x=son;
	}
	if((2*x==he)&&(dist[heap[x]]>dist[heap[2*x]])) replace(x,2*x);
}

void add(int dest, int val)
{
	heap[++he]=dest;
	dist[dest]=val;
	poz[dest]=he;
	up(he);
}

void erase()
{
	replace(1,he);
	--he;
	down(1);
}
void dijkstra(int source)
{
	int min;
	//adaug in heap sursa avand dist 0
	heap[1]=1;
	poz[1]=1;
	dist[1]=0;
	
	//cat timp am elemente in heap
	while(he)
	{
		min=heap[1];
		//extrag nodul 1 cu distanta minima din heap si actualizez heapul
		erase();
		
		//pentru fiecare y vecin al nodului extras
		for(int i=1;i<=d[min][0];++i)
		{
			//daca vecinul curent nu a mai fost atins il adaug in heap
			if(dist[d[min][i]]<0)
				add(d[min][i],dist[min]+c[min][i]);
			else
				//daca pot imbunatati
				if(dist[d[min][i]]>dist[min]+c[min][i])
				{
					dist[d[min][i]]=dist[min]+c[min][i];
					up(poz[d[min][i]]);
				}
		}
	}
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	int i;
	for(i=0;i<m;++i){
		scanf("%d%d%d",&drum[i].s,&drum[i].d,&drum[i].c);
		++dist[drum[i].s];
	}
	
	for(i=1;i<=n;++i){
		d[i]=new int[dist[i]+1];
		c[i]=new int[dist[i]+1];
		poz[i]=dist[i]=-1;
		d[i][0]=0;
	}
	
	for(i=0;i<m;++i){
		d[drum[i].s][++d[drum[i].s][0]]=drum[i].d;
		c[drum[i].s][d[drum[i].s][0]]=drum[i].c;
	}
	
	dijkstra(1);
	
	for(i=2;i<=n;++i)
	{
		if(dist[i]!=-1)
			printf("%d ",dist[i]);
		else
			printf("0 ");
	}
	printf("\n");
	return 0;
}