// This program was written on 28.03.2022
// for problem dijkstra
// by Mircea Rebengiuc

// dijkstra fara heap de mana -- implementare olimpiada

#include <stdio.h>
#include <ctype.h>

#include <set>// implementam cu set (RBT) ca pq din stl nu are funcite de update
#include <vector>// vector dimensionat la runtime

#define MAXN 50000
#define INF 2000000000

std::vector<std::pair<int, int>> adj[MAXN];
std::set<std::pair<int, int>> heap;
int dist[MAXN];
int viz[MAXN];

FILE *fin, *fout;

static inline int fgetint(){
  int n = 0, ch, semn = 1;

  while( isspace(ch = fgetc(fin)) );
  if( ch == '-' ){
    semn = -1;
    ch = fgetc(fin);
  }
  do
    n = n * 10 + ch - '0';
  while( isdigit(ch = fgetc(fin)) );

  return n * semn;
}

static inline int min( int a, int b ){
  return a < b ? a : b;
}

int main(){
  fin  = fopen( "dijkstra.in",  "r" );
  fout = fopen( "dijkstra.out", "w" );
  
  int n, i, m, a, b;
  
  n = fgetint();
  
  for( i = 0 ; i < n ; i++ ){
    viz[i] = 0;
    dist[i] = +INF;
  }
  
  for( m = fgetint() ; m-- ; ){
    a = fgetint() - 1;
    b = fgetint() - 1;
    
    adj[a].push_back( std::make_pair( b, fgetint() ) );
  }
  
  heap.insert( std::make_pair( 0, 0 ) );
  dist[0] = 0;
  while( !heap.empty() ){
    a = (*heap.begin()).second;
    heap.erase( heap.begin() );
    viz[a] = 1;
    
    for( auto e : adj[a] )
      if( !viz[e.first] ){
        if( dist[e.first] < +INF )
          heap.erase( std::make_pair( dist[e.first], e.first ) );
        
        dist[e.first] = min( dist[e.first], dist[a] + e.second );
        heap.insert( std::make_pair( dist[e.first], e.first ) );
      }
  }
  
  for( i = 1 ; i < n ; i++ )
    fprintf( fout, "%d ", dist[i] < INF ? dist[i] : 0 );
  
  fputc( '\n', fout );
  
  fclose( fin );
  fclose( fout );
  return 0;
}