#include <fstream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <stack>
#include <vector>


#define NMAX  50005
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define INF 0x3f3f3f3f

using namespace std;

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

priority_queue< pair < int , int > , vector < pair < int , int > > , greater < pair < int , int  > > > Dijkstra_Heap;
int N , M ,Cost[NMAX];
vector < pair < int, int > > Graph[NMAX];


void Read( void ){
    int i , start_node , final_node , cost;
    in >> N >> M ;
    for ( i = 1 ; i <= N ; ++i ){
       in >> start_node >> final_node >> cost;
       Graph[start_node].push_back(make_pair(final_node,cost));
    }
}

void MakeDijkstra ( void ){
   memset ( Cost , INF , sizeof(Cost)) , Cost[1] = 0 ;
   Dijkstra_Heap.push(make_pair(0,1));
   while ( !Dijkstra_Heap.empty()){
     int cost , node ;
     cost = Dijkstra_Heap.top().first;
     node = Dijkstra_Heap.top().second;
     Dijkstra_Heap.pop();
     for ( vector < pair < int , int > > ::iterator it = Graph[node].begin() ; it != Graph[node].end() ; ++it )
         if (  cost + it->second < Cost[it->first]){
         Cost[it->first] = cost + it->second;
         Dijkstra_Heap.push(make_pair(Cost[it->first],it->first));
         }
   }
}
void PutSol ( void ){
    int i ;
    for ( i = 2 ; i <= N ; ++i )
      out << ( Cost[i] != INF ? Cost[i] : 0 ) <<  " ";

}

int main()
{
    Read();
    MakeDijkstra();
    PutSol();
    return 0;
}