#include<cstdio>
#include<vector>
#define pinf (1<<30)
using namespace std;
void citire(),dijkstra(),afisare();
vector<vector<int> >a(1000,vector<int>(1000));
//int a[100][100];
vector<int>T(100),V(100),D(100);
int n,m,s;
int main()
{
    citire();
    dijkstra();
    afisare();
    return 0;
}
void citire()
{
    freopen("dijkstra.in","r",stdin);
    scanf("%d%d",&n,&m);
    s=1;
    int i,j,x,y,z;
    for(i=1;i<=n;++i)
      for(j=i+1;j<=n;++j)
         a[i][j]=a[j][i]=pinf;
    for(i=1;i<=m;++i)
      scanf("%d%d%d",&x,&y,&z), a[x][y]=z;
}
void dijkstra()
{
    int i,j,min,poz;
    for(i=1;i<=n;++i)
       {
           if(a[s][i]!=pinf)
                T[i]=s;
           D[i]=a[s][i];
       }
    T[s]=0;
    D[s]=0;
    V[s]=1;

    for(i=1;i<=n ;++i)
         {
             min=pinf;
             for(j=1;j<=n; ++j)
                 if(!V[j] && (D[j]<min)) min=D[j],poz=j;
             V[poz]=1;
             for(j=1;j<=n; ++j)
                if(!V[j] && D[j]>D[poz]+a[poz][j])
                 {
                     D[j]=D[poz]+a[poz][j];
                     T[j]=poz;
                 }
         }
}
void afisare()
{
    int i;
    freopen("dijkstra.out","w",stdout);
    for(i=2;i<=n;++i)
      printf("%d ",D[i]);
}