#include <cstdio>
#include <vector>
#include <algorithm>
#define NMAX 50000
#define INF ( NMAX - 1 ) * 20000
const int NIL = -1;
using namespace std;
FILE *fin, *fout;
vector < pair<int, int> > G[NMAX];
int dist[NMAX],
    heap[NMAX], nr, unde[NMAX];
//heap[i] = indicele nodului cu costul respectiv aseazarii in heap
//unde[i] = pe ce pozitie e nodul i in heap
//indexam totul de la 0

inline int fiu( int nod ) {
  return ( nod << 1 ) + 1;
}

void down( int poz ) {
  bool ok = true;
  int fiut;
  while ( fiu( poz ) < nr && ok ) {
    fiut = fiu( poz );
    ok = false;
    if ( fiut + 1 < nr && dist[heap[fiut]] > dist[heap[fiut + 1]] )
      fiut = fiut + 1;
    if ( dist[heap[poz]] > dist[heap[fiut]] ) {
      ok = true;
      unde[heap[poz]] = fiut;
      unde[heap[fiut]] = poz;
      swap( heap[poz], heap[fiut] );
      poz = fiut;
    }

  }
}

void pop() {
  unde[heap[nr - 1]] = 0;
  unde[heap[0]] = NIL;
  swap( heap[0], heap[nr - 1] );
  nr--;
  down( 0 );
}

void up( int poz ) {
  int tata = ( poz - 1 ) >> 1;
  while ( poz != 0 && dist[heap[poz]] < dist[heap[tata]] ) {
    unde[heap[poz]] = tata;
    unde[heap[tata]] = poz;
    swap( heap[poz], heap[tata] );
    poz = tata;
    tata = ( poz - 1 ) >> 1;
  }
}

void push( int nod ) {
  heap[nr] = nod;
  unde[nod] = nr;
  nr++;
  up( nr - 1 );
}

int main() {
  fin = fopen( "dijkstra.in", "r" );
  fout = fopen( "dijkstra.out", "w" );
  int n, m, p, i, j, y, c;
  p = 0;//nodul din care facem Dijkstra
  fscanf( fin, "%d%d", &n, &m );
  while ( m-- ) {
    fscanf( fin, "%d%d%d", &i, &j, &c );
    i--; j--;
    G[i].push_back( make_pair( j, c ) );
  }
  for ( i = 1; i < n; i++ ) {
    dist[i] = INF;
    unde[i] = NIL;//nu e nimeni in heap
  }
  /*for ( j = 0; j < G[p].size(); j++ ) {
    y = G[p][j].first;
    dist[y] = G[p][j].second;
    push( y );
  }*/
  push( p );
  int varf;
  while ( nr ) {
    varf = heap[0];
    pop();
    for ( j = 0; j < G[varf].size(); j++ ) {
      y = G[varf][j].first;
      c = G[varf][j].second;
      if ( dist[y] > dist[varf] + c ) {
        dist[y] = dist[varf] + c;
        if ( unde[y] == NIL )
          push( y );
        else
          up( unde[y] );
      }
    }
  }
  for ( i = 0; i < n; i++ )
    if ( i != p ) {
      if ( dist[i] == INF )
        dist[i] = 0;
      fprintf( fout, "%d ", dist[i] );
    }
  fprintf( fout, "\n" );
  fclose( fin );
  fclose( fout );
  return 0;
}