#include <fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,s[50001],d[50001],pred[50001],MAXX=1001,x,y,c,start=1,minn,ct;
struct muchie
{
int y,c;
muchie *urm;
}*L[50001],*p,*aux2;
muchie* get_muchie(int i,int j)
{
muchie *aux;
for(aux=L[i]; aux!=NULL; aux=aux->urm)
if(aux->y==j)
return aux;
return NULL;
}
int main()
{
f>>n>>m;
for(int i=1; i<=m; i++)
{
f>>x>>y>>c;
p=new muchie;
p->y=y;
p->c=c;
p->urm=L[x];
L[x]=p;
p=new muchie;
p->y=x;
p->c=c;
p->urm=L[y];
L[y]=p;
}
s[start]=1;
for(int i=1; i<=n; i++)
{
aux2=get_muchie(start,i);
if(start==i)
d[i]=0;
else if(aux2==NULL)
d[i]=MAXX;
else
{
d[i]=aux2->c;
if(i!=start&&d[i]<MAXX)
pred[i]=start;
}
}
for(int i=1; i<=n-1; i++)
{
for(int j=1,minn=MAXX; j<=n; j++)
{
if(s[j]==0&&d[j]<minn)
{
minn=d[j];
y=j;
}
}
s[y]=1;
for(int j=1; j<=n; j++)
{
if(y!=j)
{
aux2=get_muchie(y,j);
if(aux2)
ct=aux2->c;
else ct=MAXX;
if(s[j]==0&&d[j]>d[y]+ct)
{
d[j]=d[y]+ct;
pred[j]=y;
}
}
}
}
for(int i=2; i<=n; i++)
if(d[i]!=MAXX)
g<<d[i]<<" ";
else g<<"0";
return 0;
}