#include<iostream>
using namespace std;
long int n,m,i,j,c[22000][22000],d[22000],v[22000],mi,poz;
void citire()
{
     freopen("dijkstra.in","r",stdin);
     cin>>n>>m;
     for(i=1; i<=n; i++)
      for(j=1; j<=n; j++)
       c[i][j]=10000;
     while(!feof(stdin))
           cin>>i>>j>>c[i][j];
     for(i=1; i<=n; i++)
      d[i]=c[1][i];
}
void dijkstra()
{
     d[1]=0;
     v[1]=1;
     for(i=1; i<=n-1; i++)
     {
              mi=1000;
              for(j=1; j<=n; j++)
                   if(v[j]==0 && d[j]<mi)
                   {
                           mi=d[j];
                           poz=j;
                   }
              v[poz]=1;
              for(j=1; j<=n; j++)
                   if(v[j]==0 && d[j]>d[poz]+c[poz][j]) d[j]=d[poz]+c[poz][j];
     }
}     
int main ()
{
    citire();
    dijkstra();
    freopen("dijkstra.out","w",stdout);
    for(i=2; i<=n-1; i++)
        if(d[i]!=10000) cout<<d[i]<<' ';
        else cout<<'0'<<' ';
    if(d[n]!=10000) cout<<d[n];
    else cout<<'0';
    fclose(stdin);
    fclose(stdout);
    return 0;
}