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

vector <int> A[5000], Dist[5000];
int n,i,infinit=10000,s[5000],x,y,m,j,cost,d[5000],min;

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

  
 f.close();
 
 }

void initializare()
{
	int vec;
    for(i=1;i<=n;i++)
        d[i]=infinit;		
	vec=A[1].size();
       for(i=1;i<=vec;i++)
            d[A[1][i]]=Dist[1][i];
         
          s[1]=1;
          }
                
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]+Dist[k][i])
			        d[i]=d[k]+Dist[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();
    
    initializare();
    
    dijkstra();
    
    afisare();
    
    
    
    return 0;
}