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

#define INF 0x3f3f3f3f
#define MAX_NODES 50000
#define HEAP_SIZE 65536
#define LEFT(pos) ((pos) * (2))
#define RIGHT(pos) (((pos) * (2)) + (1))
#define PARENT(pos) ((pos) / (2))

typedef struct node{
  int data;
  int weight;
  struct node * next;
} node;

node * G[MAX_NODES];
int dist[MAX_NODES];
int heap[HEAP_SIZE + 1], heapSize;
int heap_pos[MAX_NODES];

void add(int from, int to, int weight) {
  node * p = malloc(sizeof(node));
  p->data = to;
  p->weight = weight;
  p->next = G[from];
  G[from] = p;
}

void readGraph(int m, FILE * in) {
  int i;
  int to, from, weight;

  for (i = 0; i < m; i++) {
    fscanf(in, "%d %d %d", &from, &to, &weight);
    add(from - 1, to - 1, weight);
  }
}

void swap(int * a, int * b) {
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

int extractMin() {
  int min, curr_pos;

  min = heap[1];
  heap_pos[min] = -1;
  heap[1] = heap[heapSize--];
  heap_pos[heap[1]] = 1;

  curr_pos = 1;
  while ((dist[heap[curr_pos]] > dist[heap[LEFT(curr_pos)]]
        || dist[heap[curr_pos]] > dist[heap[RIGHT(curr_pos)]]
      ) && RIGHT(curr_pos) <= heapSize) {

    if (dist[heap[LEFT(curr_pos)]] <= dist[heap[RIGHT(curr_pos)]]) {
      swap(&heap[curr_pos], &heap[LEFT(curr_pos)]);
      swap(&heap_pos[heap[curr_pos]], &heap_pos[heap[LEFT(curr_pos)]]);
      curr_pos = LEFT(curr_pos);
    }
    else {
      swap(&heap[curr_pos], &heap[RIGHT(curr_pos)]);
      swap(&heap_pos[heap[curr_pos]], &heap_pos[heap[RIGHT(curr_pos)]]);
      curr_pos = LEFT(curr_pos);
    }
  }

  return min;
}

void addHeap(int node) {
  int curr_pos;

  heap[++heapSize] = node;
  heap_pos[node] = heapSize;

  curr_pos = heapSize;
  while(dist[heap[curr_pos]] < dist[heap[PARENT(curr_pos)]] && curr_pos > 1) {
    swap(&heap[curr_pos], &heap[PARENT(curr_pos)]);
    swap(&heap_pos[heap[curr_pos]], &heap_pos[heap[PARENT(curr_pos)]]);
    curr_pos = PARENT(curr_pos);
  }
}

void modifyDist(int node, int newDist) {
  dist[node] = newDist;
  int curr_pos = heap_pos[node];

  while((dist[heap[curr_pos]] < dist[heap[PARENT(curr_pos)]]) && curr_pos > 1) {
    swap(&heap[curr_pos], &heap[PARENT(curr_pos)]);
    swap(&heap_pos[heap[curr_pos]], &heap_pos[heap[PARENT(curr_pos)]]);
    curr_pos = PARENT(curr_pos);
  }
}

void dijkstra(int nodes) {
  int curr_node, i;
  node * p;

  memset(dist, INF, sizeof(dist));
  dist[0] = 0;

  for (i = 0; i < nodes; i++)
    addHeap(i);


  while (heapSize) {
    curr_node = extractMin();
    for (p = G[curr_node]; p; p = p->next) {
      if (dist[curr_node] + p->weight < dist[p->data]) {
        modifyDist(p->data, dist[curr_node] + p->weight);
      }
    }
  }

}

int main() {
  FILE * in, * out;
  int m, n, i;

  in = fopen("dijkstra.in", "r");
  fscanf(in, "%d %d", &n, &m);
  readGraph(m, in);
  fclose(in);

  dijkstra(n);

  out = fopen("dijkstra.out", "w");
  for (i = 1; i < n; i++) {
    fprintf(out, "%d ", dist[i]);
  }
  fprintf(out, "\n");
  fclose(out);

  return 0;
}