#include <fstream>

using namespace std;

fstream f;
fstream g;

int n,m,i,j;
int x,y,z;

struct nod{
   int node;
   int len;
   nod *next; 
};

nod *d;

nod *a[50001];
int S[50001];
int T[50001];
int D[50001];
 
void addNode(int from, int to, int length)
{
    d = new nod;
    d->next = a[from];
    d->node = to;
    d->len = length;
    a[from] = d;     
}


int minimum(int s,int b)
{
   int road=D[s];
   nod *aux = a[s];
   int addition=1001;
   while(aux)
   {
      if(b == aux->node)
      {
           addition=aux->len;
           break;
      }
      aux=aux->next;         
   }  

   
   road=road+addition;
   if(road>D[b])
       return D[b];
   return road;    
}

int main()
{
    f.open("dijkstra.in",fstream::in);
    f >> n >> m;
    for(i=0;i<n;i++)
     {
       f >> x >> y >> z;
                 
       addNode(x,y,z);         
     }      
    f.close();

    for(i=1;i<n;i++)
       S[1] = 1;
    
    
    g.open("dijkstra.out",fstream::out);
    nod *aux;
    nod *aux2;
    aux=a[1];
    
    for(i=2;i<=n;i++)
      D[i]=1001;
    while(aux)
    {
       D[aux->node]=aux->len;
       T[aux->node]= 1;
       aux = aux->next;
                    
    }
    
    int min,varf;
         for(i=1;i<=n;i++)
           {
               min=1001;
               for(j=2;j<=n;j++)
                   if(S[j]==0)          
                        if(min>D[j])
                          { 
                           min = D[j];
                           varf = j;
                           }
                S[varf]=1;
                for(j=2;j<=n;j++)
                   if(S[j]==0)
                      D[j]=minimum(varf,j);
           }            
           
       for(i=2;i<=n;i++)
         g << D[i] << " ";
         g<<"\n";    
    g.close();
        
    return 0;
    
}