#include <fstream.h>
const int inf=50000000;
struct nod
{int d;short c;
 nod* adr;}*l,*G[50001];
void push(int s,int d,short c)
{nod *p=new nod;
 p->d=d;p->c=c;
 p->adr=G[s];
 G[s]=p;}
short c,p[50001]={1};
int N,M,i,a,b,cd[50001]={1},in,sf,d[50001];
int main() 
{ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
f>>N>>M;
for(;i<M;++i) 
{f>>a>>b>>c;
 push(a,b,c);}
for(i=2;i<=N;++i)
 d[i]=inf;
//Q.push(1);InQueue[1] = true;
while(in<=sf) 
{a=cd[in];
 ++in;
 p[a]=0;
 l=G[a];
 while(l)
 {b=l->d;c=l->c;
  if(d[a]+c<d[b]) 
  {d[b]=d[a]+c;
   if(!p[b]) 
   {cd[++sf]=b;
	p[b]=1;}
  }
  l=l->adr;}
}
for (i=2;i<=N;++i)
	if(d[i]==inf)
	 g<<  0 <<' ';
	else
	 g<<d[i]<<' ';
return 0;
}