#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 5e4 + 1;
const int INF = 2e9;

vector<pair<int, int>> G[DIM];
int dist[DIM];

int main() {
  ios_base::sync_with_stdio(0);
  fin.tie(0);
  int n, m, u, v, c;

  fin >> n >> m;
  while ( m-- ) {
	fin >> u >> v >> c;
	G[u].push_back({v, c});
  }
  for ( int i = 1; i <= n; ++i ) {
	dist[i] = INF;
  }
  priority_queue<pair<int, int>> q;
  q.push({0, 1});
  dist[1] = 0;
  while ( !q.empty() ) {
	tie(c, u) = q.top();
	q.pop();
	if ( dist[u] + c ) continue;
	for ( auto [v, c] : G[u] ) {
	  if ( dist[v] > dist[u] + c ) {
		dist[v] = dist[u] + c;
		q.push({-dist[v], v});
	  }
	}
  }
  for ( int i = 2; i <= n; ++i ) {
	fout << (dist[i] == INF ? 0 : dist[i]) << " ";
  }
  fin.close();
  fout.close();
  return 0;
}