#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;
}

void upheap(int position) {
  while (dist[heap[position]] < dist[heap[PARENT(position)]] && position > 1) {
    swap(&heap[position], &heap[PARENT(position)]);
    heap_pos[heap[position]] = position;
    heap_pos[heap[PARENT(position)]] = PARENT(position);
    position = PARENT(position);
  }
}

void downheap(int position) {
  int l, r, i;
  if (LEFT(position) <= heapSize) {
    l = LEFT(position);
    if (RIGHT(position) <= heapSize)
      r = RIGHT(position);
    else
      r = l - 1;

    if (r < l || dist[heap[l]] < dist[heap[r]])
      i = l;
    else
      i = r;

    if (dist[heap[position]] > dist[heap[i]]) {
      swap(&heap[position], &heap[i]);
      heap_pos[heap[position]] = position;
      heap_pos[heap[i]] = i;
      downheap(i);
    }
  }
}

void addHeap(int node) {
  heap[++heapSize] = node;
  heap_pos[node] = heapSize;
  upheap(heapSize);
}

int extractMin() {
  int min = heap[1];
  heap[1] = heap[heapSize--];
  heap_pos[heap[1]] = 1;
  downheap(1);
  return min;
}

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]) {
        printf("%d\n", curr_node);
        dist[p->data] = dist[curr_node] + p->weight;
        upheap(heap_pos[p->data]);
      }
    }
  }

}

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++) {
    if (dist[i] != INF) {
      fprintf(out, "%d ", dist[i]);
    }
    else {
      fprintf(out, "0 ");
    }
  }
  fprintf(out, "\n");
  fclose(out);

  return 0;
}