#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
#define MAX_N 50000
#define INF 1e9
 
struct Edge {
  int node, cost;
};


// Beware! Invert operator here:
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();
 
    // Do not process nodes that have been already processed
    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;
          // We don't care about heap dimension, we don't update node value
          // We just add this road in the heap
          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;
}