#include <fstream>
#include <list>
#include <vector>
#define NMAX 50005

using namespace std;
long n,m,okch;

struct nod
{
	long varf;
	long cost;
	nod(){}
	nod(long nvarf,long ncost)
	{
		varf=nvarf;
		cost=ncost;
	}
};

vector<list<nod> > G;
nod d[NMAX];
long nrVf=-1;

void adaugaInHeap(nod x)
{
	long i=1,poz1,poz2;
	nod aux;
	d[++nrVf]=x;
	poz1=nrVf;
	poz2=nrVf/2;
	while(poz2>=1 && d[poz1].cost<d[poz2].cost)
	{
		aux=d[poz1];
		d[poz1]=d[poz2];
		d[poz2]=aux;
		poz1=poz2;
		poz2=poz1/2;
	}
}

long minim(long i,long j)
{
	if(d[i].cost>d[j].cost)
		return j;
	else
		return i;
}

nod minimHeap()
{
	long poz1,poz2;
	nod aux,sv=d[1];
	aux=d[1];
	d[1]=d[nrVf];
	d[nrVf]=aux;
	nrVf--;
	poz1=1;
	poz2=minim(poz1*2,poz1*2+1);
	while(poz2<=nrVf && d[poz1].cost>d[poz2].cost)
	{
		aux=d[poz1];
		d[poz1]=d[poz2];
		d[poz2]=aux;
		poz1=poz2;
		poz2=minim(poz1*2,poz1*2+1);
	}
	return sv;
}

void cautaHeap(long poz,long vf, long &svpoz)
{
	if(d[poz].varf==vf)
	{
		okch=1;
		svpoz=poz;
	}
	else
	{
		if(poz*2<=n && okch==0)
			cautaHeap(poz*2,vf,svpoz);
		if(poz*2+1<=n && okch==0)
			cautaHeap(poz*2+1,vf,svpoz);
	}
}
void updateHeap(nod elCur,nod vfCautat)
{
	long poz,poz1,poz2;
	nod aux;
	okch=0;
	cautaHeap(1,vfCautat.varf,poz);
	if(d[poz].cost>vfCautat.cost+elCur.cost)
	{
		d[poz].cost=vfCautat.cost+elCur.cost;

		poz1=poz;
		poz2=poz1/2;
		while(poz2>=1 && d[poz1].cost<d[poz2].cost)
		{
			aux=d[poz1];
			d[poz1]=d[poz2];
			d[poz2]=aux;
			poz1=poz2;
			poz2=poz1/2;
		}
	}
}
int main()
{
	long i,x,y,c;
	list<nod> lista;
	fstream fin,fout;
	fin.open("dijkstra.in",ios::in);
	fout.open("dijkstra.out",ios::out);

	fin>>n>>m;
	for(i=0;i<=n;i++)
	{
		G.push_back(lista);
		adaugaInHeap(nod(i,LONG_MAX));
	}
	for(i=1;i<=m;i++)
	{
		fin>>x>>y>>c;
		G[x].push_back(nod(y,c));
	}
	d[1].cost=0;
	list<nod>::iterator itr;
	while(nrVf>0)
	{
		nod nd = minimHeap();
		for(itr=G[nd.varf].begin(); itr!=G[nd.varf].end(); itr++)
		{
			updateHeap(nd,*itr);
		}
	}
	long poz;
	for(i=2;i<=n;i++)
	{
		okch=0;
		cautaHeap(1,i,poz);
		if(d[poz].cost==LONG_MAX)
			fout<<"0 ";
		else
			fout<<d[poz].cost<<" ";
	}
	fout<<'\n';
	fin.close();
	fout.close();
	return 0;
}