#include<iostream.h>
#include<fstream.h>
struct nod{int info,cost;
nod*next;};
nod *v[100001];
int d[100],p[100],viz[100],inf=100001,n;
void dijkstra(int x)
{nod *z;
int max,ok=1,k,i;
for(i=1;i<=n;i++)
	d[i]=inf;
for(z=v[x];z!=NULL;z=z->next)
{	d[z->info]=z->cost;
p[z->info]=x;}
viz[x]=1;
while(ok==1)
{max=inf;
for(i=1;i<=n;i++)
	if(d[i]<max&&viz[i]==0)
		{max=d[i];
	k=i;}
		if(max!=inf)
		{viz[k]=1;
		for(i=1;i<=n;i++)
if(viz[i]==0)	
for(z=v[k];z!=NULL;z=z->next)	
		if(d[k]+z->info<d[i])
				{d[z->info]=d[k]+z->cost;
		p[i]=k;}
		}
		else
		ok=0;}}
void add(int x,int y,int c)
{nod*p;
p=new nod;
p->info=y;
p->cost=c;
p->next=v[x];
v[x]=p;}
int main()
{long i,m;
long c,x,y;
nod*p;
	ifstream f("dijkstra.in");
	ofstream h("dijkstra.out");
f>>n>>m;
for(i=1;i<=m;i++)
{f>>x>>y>>c;
add(x,y,c);}
dijkstra(1);
for(i=2;i<=n;i++)
	h<<d[i]<<" ";


return 0;}