#include <cstdio>
#include <vector>
#include <queue>
#include <bitset>
#define INF 2000000000
#define nmax 50001

using namespace std;

priority_queue < pair< int, int> > coada;
vector < pair< int, int> > v[nmax];
int d[nmax];
bitset <nmax> verif;

void init( int nr_nod ) {
  for ( int i = 2; i<= nr_nod; i++ )
    d[i] = INF;
}

void dijkstra( int nod_start, int nr_nod ) {
  int nod;
  init( nr_nod );
  coada.push( make_pair( 0, nod_start ) );
  while ( coada.empty() == 0 ) {
    nod = coada.top().second;
    if ( verif[nod] == 0 ) {
      verif[nod] = 1;
      for ( auto i : v[nod] ) {
        if( d[nod] + i.second < d[i.first] ) {
          d[i.first] = d[nod] + i.second;
          coada.push( make_pair( -d[i.first], i.second ) );
        }
      }
    }
    coada.pop();
  }
}

int main() {
  int nr_nod, nr_muchii, i, a, b, c;
  FILE *fin, *fout;
  fin = fopen( "dijkstra.in", "r" );
  fscanf( fin, "%d%d", &nr_nod, &nr_muchii );
  for ( i = 0; i < nr_muchii; i++ ) {
    fscanf( fin, "%d%d%d", &a, &b, &c );
    v[a].push_back( make_pair( b, c ) );
  }
  fclose( fin );

  dijkstra( 1, nr_nod );

  fout = fopen( "dijkstra.out", "w" );
  for ( i = 2; i <= nr_nod; i++ )
    if ( d[i] != INF )
      fprintf( fout, "%d ", d[i] );
    else
      fprintf( fout, "0 " );
  fputc( '\n', fout );
  fclose( fout );
  return 0;
}