#include <iostream>
#include <list>
#define XS(a,b) a^=b^=a^=b
#define NMAX 50005
#define DMAX 0xfffffff

using namespace std;
typedef struct _nod{int fiu,cost;_nod* next;}*lista;

void init(int vector[],int valoare),citire(),rezolvare(),afisare();
int N,M,iHeap,heap[NMAX],distanta[NMAX],pozitie[NMAX];
lista G[NMAX];

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
	init(distanta,DMAX);
	init(pozitie,-1);
	
	citire();
	rezolvare();
	afisare();
	
	return 0;
}

void afisare()
{
	for(int i=2;i<=N;i++)
		if(distanta[i]^DMAX)
			printf("%d ",distanta[i]);
		else
			printf("0 ");
}

void Down(int tata)
{
	for(int fiu=tata?tata<<1:1;;fiu=tata<<1)
	{
		if((fiu+1)<iHeap&&distanta[heap[fiu+1]]<distanta[heap[tata]])
			fiu++;
		else if(fiu>=iHeap)
			return;
		XS(pozitie[heap[fiu]],pozitie[heap[tata]]),
		XS(heap[fiu],heap[tata]),
		tata=fiu;
	}
}

int Pop()
{
	int nod=heap[0];
	pozitie[nod]=-1;
	heap[0]=heap[--iHeap];
	pozitie[heap[0]]=0;
	Down(0);
	return nod;
}

void Up(int fiu)
{
	for(int tata=fiu>>1;fiu&&distanta[tata]>distanta[fiu];fiu>>=1,tata=fiu>>1)
		XS(pozitie[heap[fiu]],pozitie[heap[tata]]),
		XS(heap[fiu],heap[tata]);
}

void Push(int nod,int dist)
{
	distanta[nod]=dist;
	if(pozitie[nod]==-1)
		pozitie[nod]=iHeap,
		heap[iHeap++]=nod;
	Up(pozitie[nod]);
}

void rezolvare()
{
	Push(1,0);
	while(iHeap)
	{
		int nodTata=Pop();
		for(lista nod=G[nodTata];nod;nod=nod->next)
			if(distanta[nod->fiu]>distanta[nodTata]+nod->cost)
				distanta[nod->fiu]=distanta[nodTata]+nod->cost,
				Push(nod->fiu,distanta[nod->fiu]);
	}
}

void citire()
{
	int s,d,c;
	scanf("%d %d",&N,&M);
	for(int i=0;i<M;i++)
	{
		scanf("%d %d %d",&s,&d,&c);
		lista aux=new _nod;
		aux->fiu=d;
		aux->cost=c;
		aux->next=G[s];
		G[s]=aux;
	}
}

void init(int vector[],int valoare)
{
	for(int i=0;i<NMAX;i++)
		vector[i]=valoare;
}