#include <cstdio>
#include <climits>
#include <vector>
#include <queue>

using std::priority_queue;
using std::vector;

const int MAX_M = 250000;
const int MAX_N = 50000;
const int INF = INT_MAX;

typedef struct {
  int next;
  unsigned short int v, cost;
} list;

struct pair {
  int u, cost;

  pair() {

  }

  pair(int u, int cost) {
    this -> u = u;
    this -> cost = cost;
  }
};

int N, M;
int d[MAX_N + 1];
list l[MAX_M + 1];
int adj[MAX_N + 1];

typedef struct {
  bool operator()(const pair &a, const pair &b) {
    return a.cost > b.cost;
  }
} minHeap;

priority_queue <pair, vector <pair>, minHeap> heap;

void addEdge(int u, int v, int cost, int pos) {
  l[pos].v = v;
  l[pos].cost = cost;
  l[pos].next = adj[u];
  adj[u] = pos;
}

void init() {
  int u;
  for (u = 1; u <= N; u++) {
    d[u] = INF;
  }
}

void dijkstra(int S) {
  int pos, v;
  d[S] = 0;
  heap.push(pair(S, 0));
  while (!heap.empty()) {
    pair curr = heap.top();
    heap.pop();
    if (curr.cost == d[curr.u]) {
      for (pos = adj[curr.u]; pos; pos = l[pos].next) {
        v = l[pos].v;
        if (d[curr.u] + l[pos].cost < d[v]) {
          d[v] = d[curr.u] + l[pos].cost;
          heap.push(pair(v, d[v]));
        }
      }
    }
  }
}

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

  fscanf(f, "%d %d", &N, &M);
  init();
  for (i = 1; i <= M; i++) {
    fscanf(f, "%d %d %d", &u, &v, &cost);
    addEdge(u, v, cost, i);
  }
  fclose(f);

  dijkstra(1);

  freopen("dijkstra.out", "w", stdout);
  for (i = 2; i <= N; i++) {
    fprintf(stdout, "%d ", (d[i] == INF) ? 0 : d[i]);
  }
  fclose(stdout);
  return 0;
}