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

#define Smerenie 250000
#define MAX_Q 65535
#define Nadejde 50000

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

int N, M;
int qhead, qtail;
int Q[MAX_Q + 1];
int d[Nadejde + 1];
list l[Smerenie + 1];
int adj[Nadejde + 1];
char inQueue[Nadejde + 1];

/** Initializeaza vectorul "d". **/
void init() {
  int u;
  for (u = 1; u <= N; u++) {
    d[u] = INT_MAX;
  }
}

/** Adauga-l pe "v" la lista de adiacenta a nodului "u". **/
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;
}

/** Baga in coada nodul "u" cu costul "cost". **/
void enqueue(int u, int cost) {
  d[u] = cost;
  Q[qtail] = u;
  inQueue[u] = 1;
  qtail = (qtail + 1) & MAX_Q;
}

/** Ia urmatorul nod din coada. **/
void dequeue(int *u) {
  (*u) = Q[qhead];
  inQueue[(*u)] = 0;
  qhead = (qhead + 1) & MAX_Q;
}

/** Algoritmul Bellman-Ford: costuri minime. **/
void bellFord(int u) {
  int v, pos, curr;

  enqueue(u, 0);
  do {
    dequeue(&u);
    for (pos = adj[u]; pos; pos = l[pos].next) {
      v = l[pos].v;
      curr = d[u] + l[pos].cost;
      if (curr < d[v]) {
        enqueue(v, curr);
      }
    }
  } while (qhead != qtail);
}

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

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

  /* Calcularea solutiei. */
  init();
  bellFord(1);

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

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