#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>

using namespace std;
const int N = 5e4;
const int M = 25e4;
const int INF = 2e9;

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

int n, m;

struct edge {
      int node, w;
};
vector <edge> edges[M+1];
bitset <N+1> visited ( false );
int dist[N+1];

struct heap_node {
      int val, poz;
} heap_min[N+1];
void init_dist () {
    for ( int i = 1; i <= n; i ++ )
       dist[i] = INF;
    dist[1] = 0;
}

void init_heap () {
    for ( int i = 1; i <= n; i ++ )
       heap_min[i].val = INF;
}



static inline int father ( int node ) {
      return ( node - 1 ) >> 1;
}
static inline int left_son ( int node ) {
      return node * 2 + 1;
}
static inline int right_son ( int node ) {
      return node * 2 + 2;
}

int min_son ( int node ) {
   if ( heap_min[left_son(node)].val < heap_min[right_son(node)].val )
     return left_son ( node );
   return right_son ( node );
}

int k = 0;
void add_heap ( int x, int node_poz ) {
    heap_min[k].val = x, heap_min[k].poz = node_poz;
    int heap_ind = k;
    while ( heap_ind && heap_min[heap_ind].val < heap_min[father(heap_ind)].val ){
       swap ( heap_min[heap_ind].val, heap_min[father(heap_ind)].val );
       swap ( heap_min[heap_ind].poz, heap_min[father(heap_ind)].poz );
       heap_ind = father ( heap_ind );
    }
    k ++;
}

void erase_heap () {
    swap ( heap_min[0].val, heap_min[k-1].val );
    swap ( heap_min[0].poz, heap_min[k-1].poz );
    k --;

    int heap_ind = 0;
    int ind_min_son = min_son ( 0 );
    while ( heap_ind < father ( k - 1 ) && heap_min[heap_ind].val > ind_min_son ) {
       swap ( heap_min[heap_ind].val, heap_min[ind_min_son].val );
       swap ( heap_min[heap_ind].poz, heap_min[ind_min_son].poz );
       heap_ind = ind_min_son;
    }
}

void dijkstra () {
    add_heap ( 0, 1 );
    while ( k ) { /// mai sunt elemente in heap
       int start_node = heap_min[0].poz;
       erase_heap ();
       if ( !visited[start_node] ) {
         visited[start_node] = true;
         for ( int i = 0; i < (int)edges[start_node].size (); i ++ )
            if ( dist[start_node] + edges[start_node][i].w < dist[edges[start_node][i].node] ) {
              dist[edges[start_node][i].node] = dist[start_node] + edges[start_node][i].w;
              add_heap ( dist[edges[start_node][i].node], edges[start_node][i].node );
            }
       }
    }
}

int main()
{

   fin >> n >> m;
   for ( int i = 1; i <= m; i ++ ) {
      int a, b, w;
      fin >> a >> b >> w;
      edges[a].push_back ( {b ,w} );
   }

   init_heap();
   init_dist();
   dijkstra();

   for ( int i = 2; i <= n; i ++ )
      fout << dist[i] << ' ';
   fout << '\n';
    return 0;
}