#include <bits/stdc++.h>
#define infi 2000000000
#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()
{
      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();
            used[node ] = false;
        q.pop();
            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 ;
}