#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin( "dijkstra.in" );
ofstream fout( "dijkstra.out" );

const int MaxN = 50002;
const int MaxCost = 2000000002;

vector<int> G[MaxN];
vector<int> cost[MaxN];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
int dist[MaxN];

void dijkstra( int stNode ) {
  int node;

  q.push( { 0, stNode } );
  dist[1] = 0;
  while ( !q.empty() ) {
	node = q.top().second;
	q.pop();
	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]; 
		q.push( { dist[G[node][i]], G[node][i] } );
	  }
	}
  }
}


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;
  }
  dijkstra( 1 );
  for ( int i = 2; i <= n; ++i ) {
	if ( dist[i] != MaxCost ) {
	  fout << dist[i] << " ";
	} else {
	  fout << 0 << " ";
	}
  }
  fin.close();
  fout.close();
  return 0;
}