#include <iostream>
#include <fstream>
#include <queue>

const int MAXN = 50 * 1000;
const int INF = 1e9;

struct Edge {
  int u, cost;
};
std::vector<Edge> adj[MAXN];

int dist[MAXN];

void dijkstra( int n, int src ){
  for( int u = 0 ; u < n ; u++ )
    dist[u] = +INF;
  dist[src] = 0;

  std::priority_queue<std::pair<int, int>> pq;
  pq.push( { 0, src } );

  while( !pq.empty() ){
    auto top = pq.top();
    int u = top.second;

    pq.pop();

    if( dist[u] == -top.first ){
      for( Edge e : adj[u] ){
        if( dist[u] + e.cost < dist[e.u] ){
          dist[e.u] = dist[u] + e.cost;
          pq.push( { -dist[e.u], e.u } );
        }
      }
    }
  }
}

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

int main(){
  int n, m;
  fin >> n >> m;

  for( int i = 0 ; i < m ; i++ ){
    int a, b, c;

    fin >> a >> b >> c;

    a--;
    b--;

    adj[a].push_back( Edge{ b, c } );
  }

  dijkstra( n, 0 );

  for( int i = 1 ; i < n ; i++ )
    fout << dist[i] << ' ';
  fout << '\n';

  return 0;
}