#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)
			cout<<nounitbuf<<distanta[i]<<" ";
		else
			cout<<nounitbuf<<"0 ";
}

void Down(int tata)
{
	for(int s=tata<<1,d=s+1;s<iHeap;s=tata<<1,d=s+1)
	{
		int aux;
		if(d<iHeap&&distanta[heap[d]]<distanta[heap[tata]])
			aux=d;
		else if(distanta[heap[s]]<distanta[heap[tata]])
			aux=s;
		else
			return;
		
		XS(pozitie[heap[aux]],pozitie[heap[tata]]),
		XS(heap[aux],heap[tata]),
		tata=aux;
	}
}

int Pop()
{
	int nod=heap[0];
	heap[0]=heap[--iHeap];
	pozitie[heap[0]]=0;
	Down(0);
	pozitie[nod]=-1;
	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;
}