#include<iostream.h>
#include<fstream.h>
int a[100][100],v[100],s[100],i,j,k,n,m,inf=1<<30,min,poz;
int main()
{
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
fin>>n>>m;
for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)a[i][j]=inf;
for(i=1;i<=m;i++)fin>>j>>k>>a[j][k];
s[1]=1;
for(i=1;i<=n;i++)v[i]=a[1][i];
for(i=2;i<=n;i++)
   {
   poz=0;
   min=inf;
   for(j=2;j<=n;j++)if(!s[j] && v[j]<min){
                                         min=v[j];
                                         poz=j;
                                         }
   s[poz]=1;
   if(poz)for(j=2;j<=n;j++)if(v[j]>v[poz]+a[poz][j])v[j]=v[poz]+a[poz][j];
   }
for(i=2;i<=n;i++)fout<<v[i]<<' ';
return 0;
}