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

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

struct Edge {
  int u, cost;

  Edge( int u, int cost ): u( u ), cost( 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 )
      continue;

    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].emplace_back( b, c );
  }

  dijkstra( n, 0 );

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

  return 0;
}