#include<fstream>
using namespace std;
int n,m,d[50005],h[50005],viz[50005],k,mn,poz[50005];
const int inf=1<<30;
typedef
struct nod
{
	int nr,cost;
	nod*urm;
}*Pnod;
Pnod l[50005];
void citire()
{
	ifstream fin("dijkstra.in");
	fin>>n>>m;
	int i,j,c;
	Pnod p;
	while(fin>>i>>j>>c)
	{
		p=new(nod);
		p->nr=j;
		p->cost=c;
		p->urm=l[i];
		l[i]=p;
	}
	fin.close();
}
void jos()
{
	int fiu,var;
	do
	{
		fiu=0;
		if(poz[mn]*2<=k)
		{
			fiu=poz[mn]*2;
			if((poz[mn]*2)+1<=k&&d[(poz[mn]*2)+1]<d[poz[mn]*2])
				fiu=(poz[mn]*2)+1;
			if(d[h[fiu]]>d[h[poz[mn]]])
				fiu=0;
		}
		if(fiu!=0)
		{
			var=h[poz[mn]];
			h[poz[mn]]=h[fiu];
			h[fiu]=var;
		}
	}
	while(fiu!=0);
}
void sterg()
{
	h[poz[mn]]=h[k];
	k--;
	jos();
}

void dijstra()
{
	int i;
	for(i=2;i<=n;i++)
		d[i]=inf;
	d[1]=0;
	viz[1]=1;
	k++;
	h[k]=1;
	Pnod p;
	mn=1;;
	poz[1]=1;
	while(k!=0)
	{
		for(p=l[h[poz[mn]]];p!=NULL;p=p->urm)
		   if(viz[p->nr]==0)
			if(d[p->nr]>d[h[poz[mn]]]+p->cost)
			{
			   d[p->nr]=d[h[poz[mn]]]+p->cost;
				h[++k]=p->nr;
			}
		sterg();
		mn=h[1];
		poz[mn]=1;
		viz[mn]=1;
	}
}
int main()
{
	citire();
	dijstra();
	int i;
	ofstream fout("dijkstra.out");
	for(i=2;i<=n;i++)
		if(d[i]!=inf)
			fout<<d[i]<<" ";
		else fout<<0<<" ";
	fout<<'\n';
	fout.close();
	return 0;
}