#include <fstream>

using namespace std ;

ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

const int infinit = 2e9 ;

int a[1005][1005] , n , m ;
int cost[1005] , vizitat[1005] ;

void initilizare ()
{
  f >> n >> m ; //nr de noduri si din ce nod se pleaca
  //initializam matricea initiala cu inf
  for ( int i = 1 ; i <= n ; ++i )
    for ( int j = 1  ; j <= n ; ++j )
        if ( i == j )
            a[i][j] = 0 ; //costul e 0 de la un nod la el insusi
        else
            a[i][j] = infinit ; //initializam initial cu o valoare foarte mare
  int i , j , c ;
  for ( ; m ; --m )
    {
     int i , j , c ;
     f >> i >> j >> c ;
     a[i][j] = c ; //ii atribuim costul fiecarui arc
    }
}

void dijkstra ( int sursa ) //sursa e nodul de inceput
{
  for ( int i = 1 ; i <= n ; ++i )
      cost[i] = a[sursa][i] ; //initializam initial costul cu ce avem corespunzator initializarii ( 0 pt i = j , inf pt cele fara arc intre ele sau o valoare corespunzatoare arcului
  vizitat[sursa] = 1 ; //marcam ca nodul sursa a fost vizitat
  for( int k = 1 ; k < n ; ++k ) // de inca n - 1 ori
   {
    int minim = infinit , poz_min ;
     for ( int i = 1 ; i <= n ; ++i )
       if ( !vizitat[i] && cost[i] < minim )
         minim = cost[i] , poz_min = i ; //marcam pozitia nodului de cost minim
     for ( int i = 1 ; i <= n ; ++i )
       if ( !vizitat[i] && cost[i] > cost[poz_min] + a[poz_min][i] ) //daca nodul i n-a fost vizitat si putem imbunatati costul de la nodul sursa pana la nodul i cu costul pana la j + costul arcului (i,j)
             cost[i] = cost[poz_min] + a[poz_min][i] ; //imbunatatim
     vizitat[poz_min] = 1 ; //marcam vizitat nodul ales de cost minim initial
   }
}

int main()
{
 initilizare () ;
 dijkstra ( 1 ) ; //facem pt nodul p
 for ( int i = 2 ; i <= n ; ++i )
    if ( cost[i] != 2e9 ) //s-a imbunatatit deci s-a putut ajunge
        g << cost[i] << " " ;
    else
        g << "0 " ; //nu se poate ajunge
}