#include <fstream>
#include <iostream>
#include <string.h>

using namespace std;
struct nod {
  nod* next;
  int vec, val;
};

nod* vecini[50001];
int bestDist[50001];
int posHeap[50001];
int sizeHeap = 0;
int heap[50001];

void swap(int pos1, int pos2) {
  int aux = heap[pos1]; heap[pos1] = heap[pos2]; heap[pos2] = aux;
  posHeap[heap[pos1]] = pos1; posHeap[heap[pos2]] = pos2;
}

void insertHeap(int node, int val) {
  if (bestDist[node] == -1) {
    sizeHeap++;
    bestDist[node] = val;
    heap[sizeHeap] = node;
    posHeap[node] = sizeHeap;
  } else if (bestDist[node] > val) {
    bestDist[node] = val;
  }
  int pos = posHeap[node];
  while (pos > 1 && bestDist[heap[pos]] > bestDist[heap[pos>>1]]) {
    swap(pos, pos>>1);
    pos = pos >> 1;
  }
}

int pop_min() {
  int res = heap[1];
  swap(1, sizeHeap); sizeHeap--;
  int pos = 1;
  while ((pos<<1) <= sizeHeap) {
    cout << pos << flush;
    int posBest = pos<<1;
    if ((pos<<1) + 1 <= sizeHeap && bestDist[heap[(pos<<1)+1]] > bestDist[heap[pos<<1]])
      posBest = (pos<<1) + 1;
    if (bestDist[heap[pos]] > bestDist[heap[posBest]]) {
      swap(pos, posBest);
      pos = posBest;
    }
  }
  return res;
}

void dijkstra(nod**vecini, int n, int start = 0) {
  for (int i=0; i<n; i++) bestDist[i] = -1;
  insertHeap(start, 0);
  while (sizeHeap > 0) {
    int nextNode = pop_min();
    while (vecini[nextNode]) {
      insertHeap(vecini[nextNode]->vec, bestDist[nextNode] + vecini[nextNode]->val);
      vecini[nextNode] = vecini[nextNode]->next;
    }
  }
  for (int i=0; i<n; i++)
    if (bestDist[i] == -1) bestDist[i] = 0;
}

int main() {
  ifstream in("dijkstra.in");
  ofstream out("dijkstra.out");
  int n, m;
  in >> n >> m;
  memset(vecini, 0, sizeof(vecini));
  for (int i=0; i<m; i++) {
    int x, y, cost;
    in >> x >> y >> cost;
    x--; y--;
    nod* newNode = new nod;
    newNode->next = vecini[x];
    newNode->vec = y;
    newNode->val = cost;
    vecini[x] = newNode;
  }
  dijkstra(vecini, n);
  for (int i=1; i<n; i++)
    out << bestDist[i] << " ";
  out << endl;
  return 0;
}