#include<iostream>
#include<fstream>
using namespace std;

long a[10000][10000],n,i,infinit=1000000,s[10000],x,y,m,j,cost,start,d[10000],min;

void citire()
{ 
     ifstream f("dijkstra.in");
       f>>n>>m;
  for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)  
     a[i][j]=infinit;
     
for(i=1;i<=m;i++)
{
                 f>>x>>y>>cost;
                 a[x][y]=cost;
                 }

  
 f.close();
 
 }

void initializare()
{
     s[start]=1;
       for(i=1;i<=n;i++)
          if (a[start][i]!=infinit)   
            d[i]=a[start][i];
          else d[i]=infinit;
          
          }
                
void dijkstra()
{int gasit,min,k;
     do{
           gasit=0;
           min=infinit;
            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==1);
                                                        
}
   
void afisare()
{ 
  ofstream g("dijkstra.out");
     for(i=2;i<=n;i++)
        g<<d[i]<<" ";
   g.close();    
        }
        
        
int main()
{
    citire();
    
    
    start=1;
    
    initializare();
    
    dijkstra();
    
    afisare();
    
    
    
    return 0;
}