#include <stdio.h>
#include <vector>
#include <queue>
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];

bool wasProcessed[MAX_N];
int dist[MAX_N];
priority_queue<Edge> heap;

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

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

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

  while (!heap.empty()) {
    top = heap.top();
    heap.pop();

    if (!wasProcessed[top.node]) {
      wasProcessed[top.node] = true;

      for (Edge edge : graph[top.node])
        if (dist[edge.node] > top.cost + edge.cost) {
          dist[edge.node] = top.cost + edge.cost;
          heap.push({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;
}