using namespace std;
#include<fstream>
#define NN 50005
#define INFINIT 1<<30
int n,v[NN],d[NN],h[NN],nH;
int poz[NN];
ofstream fout("dijkstra.out");
struct nod
{
	int capat,cost;
	nod* next;
};
nod* G[NN];
void promoveaza(int);
void cerne(int);
void init(int sursa)
{
	for(int i=0;i<=n;++i)
		v[i]=0,d[i]=INFINIT,h[i]=i,poz[i]=i;
	nH=n;
	v[sursa]=1,d[sursa]=0;
	h[sursa]=h[nH--];
	poz[h[sursa]]=sursa;
	for(nod *p=G[sursa]; p; p=p->next)
	{
		d[p->capat]=p->cost;
		promoveaza(poz[p->capat]);
	}
}
void promoveaza(int k)
{
	int esteHeap=0,aux,i;
	while(!esteHeap && k/2 > 0)
	{
		i=k/2;
		if(d[h[i]] < d[h[k]])
			esteHeap=1;
		else
		{
			aux=h[i],h[i]=h[k],h[k]=aux;
			poz[h[i]]=i,poz[h[k]]=k;
			k=i;
		}
	}
}
void cerne(int k)
{
	int esteHeap=0,aux,i;
	while(2*k<=nH && !esteHeap)
	{
		i=2*k;
		if(i+1<=nH && d[h[i]] > d[h[i+1]])
			i++;
		if(d[h[k]] <= d[h[i]])
			esteHeap=1;
		else
		{
			aux=h[i];
			h[i]=h[k];
			h[k]=aux;
			poz[h[i]]=i;
			poz[h[k]]=k;
			k=i;
		}
	}
}
void dijkstra(int sursa)
{
	init(sursa);
	//int gata=0;
	for(int kkk=1;kkk<n;++kkk)
	{
		int pmin=0;
		pmin=h[1];
		if(d[pmin]==INFINIT)
			break;
		v[pmin]=1;
		h[1]=h[nH--];
		poz[h[1]]=1;
		cerne(1);
		for(nod* p=G[pmin];p;p=p->next)
			if(v[p->capat]==0)
				if(d[p->capat]>d[pmin]+p->cost)
					d[p->capat]=d[pmin]+p->cost;
	}
}
void addarc(int i,int j,int c)
{
	nod *p=new nod;
	p->capat=j;
	p->cost=c;
	p->next=G[i];
	G[i]=p;
}
int main()
{
	int i,j,cost,m;
	ifstream fin("dijkstra.in");
	fin>>n>>m;
	for(;m;--m)
	{
		fin>>i>>j>>cost;
		addarc(i,j,cost);
	}
	fin.close();
	dijkstra(1);
	for(int i=2;i<=n;++i)
		if(d[i]==INFINIT)
			fout<<0<<' ';
		else
		   fout<<d[i]<<' ';
	fout.close();
	return 0;
}