#include<fstream>
using namespace std;

long n,i, j;
long a[500][500], d[500],s[500];
void citire()
{
  long m,i, j, x, y, cost;
     ifstream f("dijkstra.in");
        f>>n>>m;
        
     /* for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
          a[i][j]=1001;*/
            
     for(i=1;i<=m;i++)
     {
       f>>x>>y>>cost;  
       a[x][y]=cost;
     }
     f.close();
}

void initializare()
{
     d[1]=0;
     s[1]=1;
     
     for(i=1;i<=n;i++)
       if(a[1][i]<1001)
          d[i]=a[1][i];
}

void dijkstra()
{
     long min,k, i, gasit;
     do{
        gasit=0;
        min=1001;
        
        for(i=1;i<=n;i++)
          if(s[i]==0&&d[i]<min)
             {
               min=d[i];
               k=i;
               gasit=1;
             } 
         s[k]=1;
         for(i=1;i<=n;i++)
           if(d[i]>d[k]+a[k][i])
              d[i]=d[k]+a[k][i];
              
              }while(gasit);    
}
          
void afisare()
{
   ofstream g("dijkstra.out");
      for(i=2;i<=n;i++)
        g<<d[i]<<" ";
   g.close();
}
  
int main()
{
    citire();
    initializare();
    dijkstra();
    afisare();
    return 0;
}