#include<iostream.h> 
#include<fstream.h> 
long long a[9000][9000]; 
int main() 
{int i,j,k,n,m,x,y,z; 
ifstream f("dijkstra.in"); 
ofstream h("dijkstra.out"); 
f>>n>>m; 
for(i=1;i<=n;i++) 
for(j=1;j<=n;j++) 
a[i][j]=10000; 
for(i=1;i<=m;i++) 
{   f>>x>>y>>z; 
a[x][y]=z;} 
for(k=1;k<=n;k++)    
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) 
if(a[i][k]+a[k][j]<a[i][j]&&a[k][j]!=10000&&a[i][k]!=10000) 
a[i][j]=a[i][k]+a[k][j]; 
for(i=2;i<=n;i++) 
h<<a[1][i]<<" "; 
return 0;}