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

#define MAX_N 50000
#define INF 1e9

struct Edge {
  int node, cost;
};

inline bool operator<(const Edge& e1, const Edge& e2) {
  return e1.cost > e2.cost;
}

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

int dist[MAX_N];
set<Edge> heap;

void dijkstra(int node) {
  int i;
  Edge top;
  set<Edge>::iterator it;

  for (i = 0; i < noNodes; ++i)
    dist[i] = INF;

  heap.insert({node, 0});
  dist[node] = 0;

  while (!heap.empty()) {
    top = *heap.begin();
    heap.erase(heap.begin());

    for (Edge edge : graph[top.node])
      if (dist[edge.node] > edge.cost + top.cost) {
        it = heap.find({edge.node, dist[edge.node]});
        if (it != heap.end())
          heap.erase(it);

        dist[edge.node] = edge.cost + top.cost;
        heap.insert({edge.node, edge.cost + top.cost});
      }
  }
}

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