#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;
}

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;
    if ( pos[this_node] == -1 ) {
      min_heap[k].value = this_value;
      min_heap[k].node = this_node;
      p = k, k ++;
      pos[this_node] = p;
    }
    else {
      min_heap[pos[this_node]].value = this_value;
      p = pos[this_node];
    }

    while ( p > 0 && min_heap[p].value < min_heap[father ( p, D_ary )].value ) {
       swap ( pos[min_heap[p].node], pos[min_heap[father ( p, D_ary )].node] );
       swap ( min_heap[p].value, min_heap[father ( p, D_ary )].value );
       swap ( min_heap[p].node, min_heap[father ( p, D_ary )].node );
       p = father ( p, D_ary );
    }
}


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;
    }

    swap ( min_heap[0].value, min_heap[k-1].value );
    swap ( min_heap[0].node, min_heap[k-1].node );
    k --;

    int p = 0;
    int chosen_child = p * D_ary + min_child ( p, D_ary );
    while ( p * D_ary + D_ary < k && min_heap[p].value > min_heap[chosen_child].value ) {
       swap ( pos[min_heap[p].node], pos[min_heap[chosen_child].node] );
       swap ( min_heap[p].value, min_heap[chosen_child].value );
       swap ( 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 ) {
      chosen_child = p * D_ary + min_child ( p, D_ary );
      if ( min_heap[p].value > min_heap[chosen_child].value ) {
        swap ( pos[min_heap[p].node], pos[min_heap[chosen_child].node] );
        swap ( min_heap[p].value, min_heap[chosen_child].value );
        swap ( min_heap[p].node, min_heap[chosen_child].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 );

       if ( visited[min_node] == false ) {
         visited[min_node] = true;
         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] << ' ';
   }

    return 0;
}