#include<fstream.h>
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int a[100][100],s[200],max=999999,d[200],p[200],n,m;
void citire(){
int i,j,x,y,c;
f>>n>>m;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++)
a[i][j]=max;
a[i][i]=0;
}
for(i=1;i<=m;i++)
f>>x>>y>>c,a[x][y]=c;
}

void dijkstra(){
int i,j,min,y,k;
s[1]=1;

for(i=1;i<=n;i++){
d[i]=a[1][i];
if(a[1][i]<max)
p[i]=1;
}

for(i=1;i<=n;i++){
for(j=1,min=max;j<=n;j++)
if(s[j]==0&&d[j]<min)
min=d[j],y=j;

s[y]=1;

for(k=1;k<=n;k++)
if(s[k]==0&&d[k]>d[y]+a[y][k])
p[k]=y,d[k]=d[y]+a[y][k];
}
}

void afis(){
int i;
for(i=2;i<=n;i++)
g<<d[i]<<' ';
g<<'\n';
}

int main(){
citire();
dijkstra();
afis();
g.close();
return 0;
}