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

struct HeapCmp {
  bool operator()(int a, int b) {
    return dist[a] < dist[b] || (dist[a] == dist[b] && a < b);
  }
};
set<int, HeapCmp> heap;

void dijkstra(int node) {
  int i, top;
  set<int>::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])
      if (dist[edge.node] > edge.cost + dist[top]) {
        it = heap.find(edge.node);
        if (it != heap.end())
          heap.erase(it);

        dist[edge.node] = edge.cost + dist[top];
        heap.insert(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;
}