#include<fstream>
using namespace std;
fstream f1,f2;
struct vecin
{
	int nr,cost;
	vecin *leg;
};
vecin *lista[50001];
int  n,d[50001];
char viz[50001];
struct candidat
{
	int nr;
	candidat *leg;
};
candidat *start;
void init_vecin()
{
	int i;
	for(i=1;i<=50000;i++) lista[i]=NULL;
}
void init_candidat()
{
	start=NULL;
}
void adaug_vecin(int u,int v,int c)
{
	vecin *p;
	p=new vecin;
	p->nr=v;
	p->cost=c;
	p->leg=lista[u];
	lista[u]=p;
}
void adaug_candidat(int v)
{
	candidat *p;
	p=new candidat;
	p->nr=v;
	p->leg=start;
	start=p;
}
void sterg_candidat(candidat *adr)
{
	candidat *p;
	if(adr==NULL)
	{
		p=start;
		start=start->leg;
		delete p;
	}
	else
	{
		p=adr->leg;
		adr->leg=p->leg;
		delete p;
	}
}
int main()
{
candidat *p,*aa,*bb;
vecin *cc;
int n,m,inf,x,y,i,nrc,c,vmin;
inf=1000000000;
f1.open("dijkstra.in",ios::in);
f2.open("dijkstra.out",ios::out);
init_vecin();
f1>>n>>m;
for(i=1;i<=m;i++)
{
	f1>>x>>y>>c;
	adaug_vecin(x,y,c);
	//adaug_vecin(y,x,c);
}
for(i=1;i<=n;i++)
{
	viz[i]=0;
	d[i]=inf;
}
d[1]=0;
viz[1]=2;
adaug_candidat(1);
nrc=1;
while(nrc)
{
	vmin=inf;
	aa=NULL;
	bb=start;
	while(bb)
	{
		x=bb->nr;
		if(d[x]<vmin)
		{
			vmin=d[x];
			p=aa;
		}
		aa=bb;
		bb=bb->leg;
	}
	if(p==NULL)
		x=start->nr;
	else
		x=p->leg->nr;
	sterg_candidat(p);
	nrc--;
	viz[x]=1;
	cc=lista[x];
	while(cc)
	{
		y=cc->nr;
		c=cc->cost;
		if(viz[y]==0)
		{
			d[y]=d[x]+c;
			viz[y]=2;
			adaug_candidat(y);
			nrc++;
		}
		else
			if(viz[y]==2)
				if(d[y]>d[x]+c)
					d[y]=d[x]+c;
		cc=cc->leg;
	}
}
for(i=2;i<=n;i++)
	if(d[i]<inf)
		f2<<d[i]<<" ";
	else f2<<0<<" ";
f1.close();
f2.close();
return 0;
}