#include <bits/stdc++.h>

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

#define Smerenie 250000
#define Nadejde 50000
#define Dragoste 4096

#define u16 unsigned short

struct pair {
  u16 int u;
  int cost;

  pair() {
  
  }

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

typedef struct {
  bool operator()(pair X, pair Y) {
    return X.cost > Y.cost;
  }
} minHeap;

struct list {
  u16 int v, cost;
  int next;

  list() {
  
  }

  list(int v, int cost, int next) {
    this -> v = v;
    this -> cost = cost;
    this -> next = next;
  }
};

int N, M;
int adj[Nadejde + 1];
list l[Smerenie + 1];
int d[Nadejde + 1];

char buff[Dragoste];
int ptr = Dragoste;

char getChar(FILE *f) {
  if (ptr == Dragoste) {
    fread(buff, 1, Dragoste, f);
    ptr = 0;
  }
  return buff[ptr++];
}

int freef(FILE *f) {
  int result = 0;
  char c;

  do {
    c = getChar(f);
  } while (!isdigit(c));
  do {
    result = (result << 3) + (result << 1) + c - '0';
    c = getChar(f);
  } while (isdigit(c));
  return result;
}

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

void init() {
  int u;

  for (u = 2; u <= Nadejde; u++) {
    d[u] = INT_MAX;
  }
}

void dijkstra(int u) {
  int pos;
  pair curr = pair(u, 0), next;

  priority_queue <pair, vector<pair>, minHeap> heap;
  assert(heap.empty());
  heap.push(curr);
  while (!heap.empty()) {
    curr = heap.top();
    heap.pop();
    if (curr.cost == d[curr.u]) {
      for (pos = adj[curr.u]; pos; pos = l[pos].next) {
        next = pair(l[pos].v, curr.cost + l[pos].cost);
        if (next.cost < d[next.u]) {
          d[next.u] = next.cost;
          heap.push(next);
        }
      }
    }
  }
}

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

  init();

  N = freef(f);
  for (M = freef(f); M; M--) {
    u = freef(f);
    v = freef(f);
    cost = freef(f);
    addEdge(u, v, cost, M);
  }
  fclose(f);

  dijkstra(1);

  /* Afisarea solutiei. */
  freopen("dijkstra.out", "w", stdout);
  for (u = 2; u <= N; u++) {
    fprintf(stdout, "%d ", d[u] == INT_MAX ? 0 : d[u]);
  }
  fprintf(stdout, "\n");
  fclose(stdout);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}