#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 sus(int caut)
{
	int var;
	while((caut>1)&&(d[h[caut]]<d[h[caut/2]]))
	{
		poz[h[caut]]=caut/2;
		poz[h[caut/2]]=caut;
		var=h[caut];
		h[caut]=h[caut/2];
		h[caut/2]=var;
		caut=caut/2;
	}
}
void jos()
{
	int fiu,var,caut;
	caut=1;
	do
	{
		fiu=0;
		if(caut*2<=k)
		{
			fiu=caut*2;
			if((caut*2)+1<=k&&(d[h[(caut*2)+1]]<d[h[caut*2]]))
				fiu=(caut*2)+1;
			if(d[h[fiu]]>=d[h[caut]])
				fiu=0;
		}
		if(fiu!=0)
		{
			var=h[caut];
			h[caut]=h[fiu];
			h[fiu]=var;
			poz[h[caut]]=caut;
			poz[h[fiu]]=fiu;
			caut=fiu;
			
			
		}
	}
	while(fiu!=0);
}
void sterg()
{
	h[1]=h[k];
	poz[h[k]]=1;
	k--;
	if(k!=0)
	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)
	{
	mn=h[1];
	sterg();
	for(p=l[mn];p!=NULL;p=p->urm)
	{
		if(d[p->nr]>d[mn]+p->cost)
		{
			 d[p->nr]=d[mn]+p->cost;
			 if(poz[p->nr]==0)
			 {
				 h[++k]=p->nr;
				 poz[p->nr]=k;
				 sus(k);
			 }
			 else
				 sus(poz[p->nr]);
		}
		
	}
	
	}
}
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;
}