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

#define NMAX 50000
#define INFINIT 1 << 31

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> s ;
long long dist [ NMAX + 1 ] ;

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

int main() {

  FILE *fin, *fout ;
  fin = fopen ("dijkstra.in", "r" ) ;
  fout = fopen ("dijkstra.out", "w" ) ;
  int n, m, i, u, v, c ;
  fscanf (fin, "%d%d", &n, &m ) ;
  for (i = 0 ; i < m ; i++ ) {
    fscanf (fin, "%d%d%d", &u, &v, &c ) ;
    g[u].push_back({v, c}) ;
  }
  dijkstra(1, n) ;
  for (i = 2 ; i <= n ; i++ ) {
    if (dist[i] != INFINIT )
      fprintf (fout, "%lld ", dist[i] ) ;
    else
      fprintf (fout, "0 " ) ;
  }
  return 0;
}