#include <bits/stdc++.h>
// edy face belman cu coada !
#define NN 50010
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int n , m ;
// noduri si muchii
 int costuri [ NN ];
struct nod{
int info;
int COST ;
nod *next;}*L[NN];

queue<int>q ;
// asta i coada
bool used[NN];
 // nodurile folosite

 void add (int x , int y , int cost )
 {
      // adaug pe y la lista lui x
      nod *aux = new nod ;
      // aloc mem
      aux -> info = y ;
      aux ->COST = cost;
      aux -> next = L[x];
      L[x]=aux;
 }

 void hai_sa_citesc()
 {
      in >> n >> m ;
         for ( int i = 1 ; i <= m ; ++ i )
         {
             int x, y ,cost;
             in >> x >> y>>cost ;
             add(x,y,cost);
         }
 }



int main()
{ int infi= INT_MAX;
      hai_sa_citesc();
      q.push(1);
    used[1] = true ;
    costuri[1]=0;
      //pai de la 1 incep !
        for ( int i = 2; i <= n ; ++ i )
                costuri[i] = infi;
          // am pus si costurile aici
          //asa s la inceput
          // acum belman


          while( !q.empty() )
        {   int node = q.front();
        q.pop();
         used[node]= false;
            for ( nod *aux = L[node] ; aux ; aux = aux ->next)
            {
                if( costuri[aux->info]>costuri[node]+aux->COST)
                      {costuri[aux->info] = costuri[node]+aux->COST;


                if (!used[aux->info])
                {
                    q.push(aux->info);
                    used[aux->info] = true ;
                }
               }
            }
        }

for ( int i = 2; i <= n ; ++ i )
     if(costuri[i] !=infi)
       out << costuri[i]<<" ";
else out << 0<<" ";



    return  0 ;
}