#include <fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
unsigned m,n,a,b,c,i,negr[50005],alb[50005];
struct nod{
	unsigned x,cost;
	nod *urm;
}*v[50005];
nod *p;
int main()
{
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		p=new nod;
		f>>a>>b>>c;
		p->x=b;
		p->cost=c;
		p->urm=v[a];
		v[a]=p;
	}
	bool ok=true;
	while (ok)
	{
		ok=false;
		for(i=1;i<=n;i++)
			if((i==1||alb[i])&&!negr[i])
			{
				negr[i]=1;
				p=v[i];
				while(p)
				{
					if((alb[p->x]==0&&((p->x)!=1))||alb[p->x]>(p->cost+alb[i]))
						alb[p->x]=alb[i]+p->cost;
					p=p->urm;
				}
				ok=true;
			}
	}
	for(i=2;i<n;i++)
		g<<alb[i]<<' ';
	g<<alb[n]<<'\n';
	
	f.close();
	g.close();
	return 0;
}