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

using namespace std;

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

const int MaxN = 50002;
const int MaxCost = (int)2e9;

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

void dijkstra( int w ) {
  int node;

  q.push({ 0, w });
  dist[w] = 0;
  while ( !q.empty() ) {
    node = q.top().second;
    q.pop();
    if ( viz[node] ) continue;
    viz[node] = 1;
    for ( auto u : G[node] ) {
      if ( dist[node] + u.second < dist[u.first] ) {
        dist[u.first] = dist[node] + u.second;
        q.push( { -dist[u.first], u.first } );
      }
    }
  }
}


int main() {
  int n, m, x, y, c;

  fin >> n >> m;
  while ( m-- ) {
  	fin >> x >> y >> c;
    G[x].push_back({ y, 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;
}