#include <stdio.h>
#include <vector>
using namespace std;

#define MAX_N 50000
#define INF 1e9

struct Edge {
  int node, cost;
};

int noNodes, noEdges;
vector<Edge> graph[MAX_N];

int dist[MAX_N];

Edge heap[MAX_N];
int graphNodeToHeapIndex[MAX_N];
int heapSize;

inline int parent(int index) { return (index - 1) / 2; }
inline int leftChild(int index) { return index * 2 + 1; }
inline int rightChild(int index) { return index * 2 + 2; }

void upHeap(int heapIndex) {
  if (heapIndex && heap[parent(heapIndex)].cost > heap[heapIndex].cost) {
    swap(heap[parent(heapIndex)], heap[heapIndex]);
    graphNodeToHeapIndex[heap[heapIndex].node] = heapIndex;
    graphNodeToHeapIndex[heap[parent(heapIndex)].node] = parent(heapIndex);

    upHeap(parent(heapIndex));
  }
}

void downHeap(int heapIndex) {
  int left, right, smallest;

  smallest = heapIndex;
  left = leftChild(heapIndex), right = rightChild(heapIndex);

  if (left < heapSize && heap[left].cost < heap[smallest].cost)
    smallest = left;
  if (right < heapSize && heap[right].cost < heap[smallest].cost)
    smallest = right;

  if (smallest != heapIndex) {
    swap(heap[heapIndex], heap[smallest]);
    graphNodeToHeapIndex[heap[heapIndex].node] = heapIndex;
    graphNodeToHeapIndex[heap[smallest].node] = smallest;

    downHeap(smallest);
  }
}

void insertHeap(int graphNode, int cost) {
  heap[heapSize] = {graphNode, cost};
  graphNodeToHeapIndex[graphNode] = heapSize;
  upHeap(heapSize++);
}

void eraseHeap(int graphNode) {
  int heapIndex;

  heapIndex = graphNodeToHeapIndex[graphNode];
  graphNodeToHeapIndex[graphNode] = -1;

  heap[heapIndex] = heap[heapSize - 1];
  graphNodeToHeapIndex[heap[heapIndex].node] = heapIndex;
  --heapSize;

  downHeap(heapIndex);
  upHeap(heapIndex);
}

// For lazy people: just use eraseHeap + insertHeap
// For people who want to impress others:
void updateHeap(int graphNode, int cost) {
  int heapIndex;

  heapIndex = graphNodeToHeapIndex[graphNode];
  heap[heapIndex].cost = cost;

  upHeap(heapIndex);
  downHeap(heapIndex);
}

inline bool isInHeap(int graphNode) { return graphNodeToHeapIndex[graphNode] != -1; }

inline const Edge& findInHeap(int graphNode) { return heap[graphNodeToHeapIndex[graphNode]]; }

inline const Edge& topHeap() { return heap[0]; }

inline bool isEmptyHeap() { return heapSize == 0; }

void dijkstra(int node) {
  int i;
  Edge top;

  for (i = 0; i < noNodes; ++i) {
    graphNodeToHeapIndex[i] = -1;
    dist[i] = INF;
  }

  insertHeap(node, 0);
  dist[node] = 0;

  while (!isEmptyHeap()) {
    top = topHeap();
    eraseHeap(top.node);

    for (Edge edge : graph[top.node])
      if (dist[edge.node] > top.cost + edge.cost) {
        dist[edge.node] = top.cost + edge.cost;

        if (isInHeap(edge.node))
          updateHeap(edge.node, dist[edge.node]);
        else
          insertHeap(edge.node, dist[edge.node]);
      }
  }
}

int main() {
  FILE *fin, *fout;
  fin = fopen("dijkstra.in", "r");
  fout = fopen("dijkstra.out", "w");

  int i, x, y, c;

  fscanf(fin, "%d%d", &noNodes, &noEdges);
  for (i = 0; i < noEdges; ++i) {
    fscanf(fin, "%d%d%d", &x, &y, &c);
    --x, --y;

    graph[x].push_back({y, c});
  }

  dijkstra(0);

  for (i = 1; i < noNodes; ++i)
    fprintf(fout, "%d ", dist[i] == INF ? 0 : dist[i]);

  fclose(fin);
  fclose(fout);
  return 0;
}