#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>

#define NMAX 50000
#define MMAX 2500000
#define INFINIT 100000000

using namespace std;


struct edge {
  int to ;
  long long cost ;
  bool operator< (const edge& a) const {
    return cost > a.cost ;
  }
};

vector <edge> g [ NMAX + 1 ] ;
priority_queue<edge> q ;
long long dist [ NMAX + 1] ;

void dijkstra (int sursa, int n ) {
  int i ;
  for (i = 1 ; i <= n ; i++)
    dist[i] = INFINIT ;
  q.push({sursa, 0}) ;
  while (!q.empty()) {
    edge next = q.top() ;
    if (dist[next.to] == INFINIT ) {
      dist[next.to] = next.cost ;
      for (auto y : g[next.to] ) {
        if (dist[y.to] == INFINIT )
          q.push({y.to, y.cost+dist[next.to]}) ;
      }
    }
    q.pop() ;
  }
}

int main() {

  FILE *fin, *fout ;
  fin = fopen ("dijkstra.in", "r" ) ;
  fout = fopen ("dijkstra.out", "w" ) ;
  int n, m, i, j, a, b ;
  long long cost ;
  fscanf (fin, "%d%d", &n, &m ) ;
  for (i = 0 ; i < m ; i++ ) {
    fscanf (fin, "%d%d%lld", &a, &b, &cost ) ;
    g[a].push_back({b, cost}) ;
  }
  dijkstra(1, n) ;
  for (i = 2 ; i <= n ; i++ )
    fprintf (fout, "%lld ", dist[i] ) ;
  return 0;
}