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

/** Sorry about this. **/
using std::pair;
using std::make_pair;
using std::priority_queue;
using std::vector;
/***********************/

/** Implementare MIN-HEAP. **/
typedef struct {
  bool operator()(pair <int, int> X, pair <int, int> Y) {
    /**
      Functia returneaza "1" daca face swap intre X si Y daca nu se respecta relatia tata->fiu.
      X = tatal iar Y = fiul. Pentru ca e MIN-HEAP inseamna X.second < Y.second.
    **/
    if (X.second < Y.second) {
      return 0;
    } else {
      return 1;
    }
  }
} minHeap;

/** pair <int, int> are 2 campuir: ".first" si ".second".
  pair <int, int> retine in ".first" nodul iar in ".second" costul nodului.
  Pot exista mai multe pair-uri cu ".first" egal!!! dar niciodata identice! **/
priority_queue <pair<int, int>, vector <pair <int, int> >, minHeap> heap;
/** I) pair <int, int> = tipul de date
    II) vector <pair <int, int> > = vectorul unde isi tine cei doi fii.
    III) minHeap = operatorul dupa care compara.
***************************/

#define MAX_N 50000

int N, M;
int d[MAX_N + 1];
vector <pair <int, int> > graf[MAX_N + 1]; // aici stii si tu.

/** Sa nu uiti de asta in viata vecilor! **/
void init() {
  int u;

  for (u = 1; u <= N; u++) {
    d[u] = INT_MAX;
  }
}

void dijkstra(int S) {
  int i, acum, vecin, costMuchie;
  pair <int, int> curr;

  init();

  d[S] = 0;
  heap.push(make_pair(S, 0));
  while (!heap.empty()) {
    /** Exact ca la coada. **/
    curr = heap.top();
    heap.pop();

    acum = curr.first;
    /** Aici e singura DIFERENTA!!! **/
    if (d[acum] == curr.second) {
      for (i = 0; i < graf[acum].size(); i++) {
        vecin = graf[acum][i].first;
        costMuchie = graf[acum][i].second;

        /** Daca costul pana acum + costul pe muchie imbunatateste costul vecinului (ca la Bellman-Ford). **/
        if (d[acum] + costMuchie < d[vecin]) {
          d[vecin] = d[acum] + costMuchie;
          heap.push(make_pair(vecin, d[vecin]));
        }
      }
    }
  }
}

int main(void) {
  int u, v, cost;
  FILE *f = fopen("dijkstra.in", "r");

  fscanf(f, "%d %d", &N, &M);
  while (M) {
    fscanf(f, "%d %d %d", &u, &v, &cost);
    graf[u].push_back(make_pair(v, cost));
    /** Poate fi si neorientat, nu conteaza. **/
    /** graf[v].push_back(make_pair(u, cost)); **/
    M--;
  }
  fclose(f);

  /** Iti alegi o sursa din care sa pornesti. **/
  dijkstra(1);

  freopen("dijkstra.out", "w", stdout);
  for (u = 2; u <= N; u++) {
    if (d[u] == INT_MAX) {
      fprintf(stdout, "%d ", 0);
    } else {
      fprintf(stdout, "%d ", d[u]);
    }
  }
  fclose(stdout);
  return 0;
}