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

using namespace std;
const int V = 5e4; /// noduri
const int E = 25e4; /// muchii
const int INF = 1e9 + 7;

int k;
struct heap_node {
      int node, value;
} min_heap[V];
int pos[V]; /// positia nodului i in heap
struct my_edge {
      int node, w;
};
vector <my_edge> edge[V];
int dist[V];
bitset<V> visited (false);

void init_inf () {
    for ( int i = 0; i < V; i ++ ) {
       min_heap[i].value = INF, pos[i] = -1;
       dist[i] = INF;
    }
}

int compute_D_ary ( int e, int v ) {
    if ( e / v < 2 )
      return 2;
    return e / v;
}

static inline int father ( int p, int D_ary ) {
   return ( p - 1 ) / D_ary;
}

int min_child ( int p , int D_ary ) {
   int return_value = INF;
   for ( int i = 1; i <= D_ary; i ++ )
      if ( p * D_ary + i < k && return_value > min_heap[p * D_ary + i].value )
        return_value = i;
   return return_value;
}

void add_heap ( int D_ary, int this_node, int this_value ) {
    int p;
    bool run_add = false;
    if ( pos[this_node] == -1 ) {
      min_heap[k].value = this_value;
      min_heap[k].node = this_node;
      p = k, k ++;
      pos[this_node] = p;

      run_add = true;
    }
    else if ( this_value < min_heap[pos[this_node]].value ) {
      min_heap[pos[this_node]].value = this_value;
      p = pos[this_node];
      run_add = true;
    }

    if ( run_add == true ) {
      int root = father ( p, D_ary );
      while ( p > 0 && this_value < min_heap[root].value ) {
         pos[min_heap[root].node] = p;
         min_heap[p].value = min_heap[root].value;
         min_heap[p].node = min_heap[root].node;
         p = root, root = father ( p, D_ary );
       }

       pos[this_node] = p;
       min_heap[p].value = this_value;
       min_heap[p].node = this_node;
    }

}


void erase_heap ( int D_ary ) {
    if ( k == 1 )
      pos[min_heap[0].node] = -1;
    else {
      pos[min_heap[0].node] = -1;
      pos[min_heap[k-1].node] = 0;
    }

    min_heap[0].value = min_heap[k-1].value;
    min_heap[0].node = min_heap[k-1].node;
    k --;

    int my_value = min_heap[0].value, my_node = min_heap[0].node;
    int p = 0, chosen_child = p * D_ary + min_child ( p, D_ary );
    while ( p * D_ary + D_ary < k && my_value > min_heap[chosen_child].value ) {
       pos[min_heap[chosen_child].node] = p;
       min_heap[p].value = min_heap[chosen_child].value;
       min_heap[p].node = min_heap[chosen_child].node;
       p = chosen_child, chosen_child = p * D_ary + min_child ( p, D_ary );
    }


    if ( p * D_ary + 1 < k ) {
      if ( my_value > min_heap[chosen_child].value ) {
        pos[min_heap[chosen_child].node] = p;
        min_heap[p].value = min_heap[chosen_child].value;
        min_heap[p].node = min_heap[chosen_child].node;
      }
      p = chosen_child;
    }

    pos[my_node] = p;
    min_heap[p].value = my_value;
    min_heap[p].node = my_node;

}

void dijkstra ( int D_ary ) {
    add_heap ( D_ary, 0, 0 );
    dist[0] = 0;
    while ( k ) {
       int min_node = min_heap[0].node;
       erase_heap ( D_ary );

       for ( int i = 0; i < (int) edge[min_node].size (); i ++ )
          if ( dist[edge[min_node][i].node] > dist[min_node] + edge[min_node][i].w ) {
            dist[edge[min_node][i].node] = dist[min_node] + edge[min_node][i].w;
            add_heap ( D_ary, edge[min_node][i].node, dist[edge[min_node][i].node] );
          }

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

int main()
{
   int v, e;
   fin >> v >> e;
   int D_ary = compute_D_ary ( e, v );

   for ( int i = 0; i < e; i ++ ) {
      int from, to, weight;
      fin >> from >> to >> weight; from --, to --;
      edge[from].push_back ( {to, weight} );
   }

   init_inf ();
   dijkstra ( D_ary );

   for ( int i = 1; i < v; i ++ ) {
      if ( dist[i] == INF )
        fout << 0 << ' ';
      else
        fout << dist[i] << ' ';
   }
   fout << '\n';

    return 0;
}