#include <fstream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
ifstream fin( "dijkstra.in" );
ofstream fout( "dijkstra.out" );
 
const int MaxN = 50002;
const int MaxCost = 2000000002;
 
struct heapNode {
  int val, vrt;
};
 
vector<int> G[MaxN];
vector<int> cost[MaxN];
heapNode heap[MaxN];
int hpos[MaxN]; 

int indH;
 
static inline int fth( int node ) {
  return (node >> 1);
}
static inline int lSon( int node ) { 
  return (node << 1);
}
static inline int rSon( int node ) {
  return ((node << 1) + 1);
}
void swp( int a, int b ) {
  swap( heap[a].val, heap[b].val );
  swap( hpos[heap[a].vrt], hpos[heap[b].vrt] );
  swap( heap[a].vrt, heap[b].vrt );
}
void repairUpp( int node ) {
  while ( node > 1 && heap[node].val < heap[fth( node )].val ) {
	swp( node, fth( node ) );
	node = fth( node );
  }
}
void repairDown( int node ) { 
  int son;	
 
  while ( node < indH ) {
	if ( lSon( node ) <= indH && rSon( node ) <= indH ) {
      if ( heap[lSon( node )].val < heap[rSon( node )].val ) {
        son = lSon( node );
	  } else {
		son = rSon( node );
	  }
	} else if ( lSon( node ) > indH && rSon( node ) <= indH ) {
	  son = rSon( node );
	} else if ( rSon( node ) > indH && lSon( node ) <= indH ) {
	  son = lSon( node );
	} else {
	  son = indH + 1;
	}
    if ( son <= indH && heap[son].val < heap[node].val ) {
      if ( son <= indH ) {
		swp( son, node );
	    node = son;
	  } else {
		node = indH + 1;
	  }
	} else {
	  node = indH + 1;
	}	
  }
}
void add( int val, int v ) {
  ++indH;
  hpos[v] = indH;
  heap[indH].val = val;
  heap[indH].vrt = v;
  repairUpp( indH );
}
void change( int pos, int val ) {
  heap[pos].val = val;
  repairUpp( pos );
  repairDown( pos );
}
void cutMin() {
  swp( indH, 1 );
  --indH;
  repairUpp( 1 );
  repairDown( 1 );
}

int dist[MaxN];
 
void dijkstra() {
  int node;
 
  add( 0, 1 );
  dist[1] = 0;
  while ( indH != 0 ) {
	node = heap[1].vrt;
	cutMin();
	for ( int i = 0; i < G[node].size(); ++i ) {
	  if ( dist[node] + cost[node][i] < dist[G[node][i]] ) {
		dist[G[node][i]] = dist[node] + cost[node][i]; 
		change( hpos[G[node][i]], dist[G[node][i]] );
		++indH;
	  }
	}
  }
}
 
 
int main() {
  int n, m, x, y, c;
  
  fin >> n >> m;
  while ( m-- ) {
	fin >> x >> y >> c;
	G[x].push_back( y );
	cost[x].push_back( c );
  }
  for ( int i = 1; i <= n; ++i ) {
	dist[i] = MaxCost;
	add( MaxCost, i );
  }
  dijkstra();
  for ( int i = 2; i <= n; ++i ) {
	if ( dist[i] != MaxCost ) {
	  fout << dist[i] << " ";
	} else {
	  fout << 0 << " ";
	}
  }
  fin.close();
  fout.close();
  return 0;
}