#include <stdio.h>
#include <string.h>

#define MAX_M 250000
#define MAX_N 50000
#define NIL -1
#define INFTY 1000000000

typedef struct {
  int v, weight;
  int next;
} cell;

cell l[MAX_M];  // liste alocate static
int adj[MAX_N]; // capetele listelor
int dist[MAX_N];

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

void bellmanFord(int u) {
  unsigned long long inQueue[MAX_N >> 6] = { };
  int q[MAX_N];
  int qStart, qEnd;

  q[0] = u;
  qStart = 0;
  qEnd = 1;

  dist[u] = 0;

  do {
    int node = q[qStart - qStart / MAX_N * MAX_N];
    qStart++;
    inQueue[node >> 6] &= ~(1ULL << (node & 63));
    for (int i = adj[node]; i != NIL; i = l[i].next) {
      if (dist[node] + l[i].weight < dist[l[i].v]) {
        dist[l[i].v] = dist[node] + l[i].weight;
        if (!(inQueue[l[i].v >> 6] & (1ULL << (l[i].v & 63)))) {
          q[qEnd - qEnd / MAX_N * MAX_N] = l[i].v;
          qEnd++;
          inQueue[l[i].v >> 6] |= (1ULL << (l[i].v & 63));
        }
      }
    }
  } while (qStart < qEnd);
}

int main(void) {
  FILE *f = fopen("dijkstra.in", "r");
  int n, m;

  fscanf(f, "%d%d", &n, &m);

  for (int i = 0; i < n; i++) {
    adj[i] = NIL;
    dist[i] = INFTY;
  }

  for (int i = 0; i < m; i++) {
    int u, v, weight;
    fscanf(f, "%d%d%d", &u, &v, &weight);
    addEdge(u - 1, v - 1, weight, i);
  }
  fclose(f);

  bellmanFord(0);

  f = fopen("dijkstra.out", "w");
  for (int i = 1; i < n; i++) {
    fprintf(f, "%d ", (dist[i] == INFTY) ? 0 : dist[i]);
  }
  fclose(f);
  return 0;
}