#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

#define MAX_N 50000
#define MAX_M 250000
#define MAX_COST 20000
#define NIL -1

typedef struct {
  int32_t v, cost, next;
} edge;

typedef std::pair<int32_t, int32_t> state;

int32_t N, M, buff, minCost = MAX_COST + 1;
int32_t adj[MAX_N + 1];
edge list[MAX_M * 2 + 1];
int32_t h[MAX_N + 1];
int32_t ksi[MAX_N + 1];

void addEdge(int32_t u, int32_t v, int32_t cost, bool inGraph) {
  ++buff;
  list[buff].v = v;
  list[buff].cost = (cost << 1) | inGraph;
  list[buff].next = adj[u];
  adj[u] = buff;
}

void bfs(int32_t s) {
  for (int32_t index = 1; index <= N; ++index)
    h[index] = NIL;

  std::queue<int32_t> queue; 
  h[s] = 0;
  queue.push(s);
  while (!queue.empty()) {
    int32_t u  = queue.front();
    queue.pop();
    for (int32_t pos = adj[u]; pos; pos = list[pos].next) {
      if (list[pos].cost & 1) {
        int32_t v = list[pos].v;
        if (h[v] == NIL) {
          h[v] = minCost * (h[u] + 1);
          queue.push(v);
        }
      }
    }
  }
}

void hyperDijkstra(int32_t s) {
  std::priority_queue<state, std::vector<state>, std::greater<state>> heap;
  
  if (minCost)
    bfs(s);
  
  for (int32_t index = 1; index <= N; ++index)
    ksi[index] = NIL;
  
  ksi[s] = h[s];
  heap.push(std::make_pair(h[s], s));
  while (!heap.empty()) {
    state curr = heap.top();
    heap.pop();
    
    int32_t u = curr.second;
    int32_t final_ = curr.first;
    if (final_ == ksi[u]) {
      for (int32_t pos = adj[u]; pos; pos = list[pos].next) {
        if (list[pos].cost & 1) {
          int32_t v = list[pos].v;
          int32_t cost = list[pos].cost >> 1;
          if ((ksi[v] == NIL) || (final_ + cost + h[v] - h[u] < ksi[v])) {
            ksi[v] = final_ + cost + h[v] - h[u];
            heap.push(std::make_pair(ksi[v], v));
          }
        }
      }
    }
  }
}

int main(/*int argc, char** argv*/) {
  std::ifstream in("dijkstra.in");
  
  in >> N >> M;
  while (M--) {
    int32_t u, v, cost;
    in >> u >> v >> cost;
    addEdge(u, v, cost, true);
    addEdge(v, u, cost, false);
    if (cost < minCost)
      minCost = cost;
  }
  in.close();
  
  hyperDijkstra(1);
  
  std::ofstream out("dijkstra.out");
  for (int32_t index = 2; index <= N; ++index)
    out << ((h[index] == NIL) ? 0 : (ksi[index] - h[index])) << " ";
  out << std::endl;
  out.close();
  return 0;
}