#include <cstdio>
#include <cstring>

#include <queue>
#include <limits>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

template <class T>
struct edge {
  T src, dst;
  double cost;

  explicit edge(T src_, T dst_, double cost_)
    : src(src_), dst(dst_), cost(cost_) {}
};

// Directed graph class
template <class T>
class digraph {
public:
  void add_node(T node) { nodes.insert(node); }

  void add_edge(T src, T dst) {
    add_node(src), add_node(dst);
    adjlist[src].emplace_back(src, dst, 0);
  }
  void add_edge(T src, T dst, double cost) {
    add_node(src), add_node(dst);
    adjlist[src].emplace_back(src, dst, cost);
  }

  // topological sort
  vector<T> topsort() const {
    unordered_map<T, int> in_degree;
    for (const auto& edges : adjlist) {
      for (const auto& e : adjlist.second)
        in_degree[e.dst]++;
    }

    queue<T> q;
    for (const auto& node : nodes)
      if (in_degree[node] == 0)
        q.push(node);

    vector<T> result;
    while (!q.empty()) {
      auto node = q.front();
      q.pop();
      result.push_back(node);

      for (const auto& e : adjlist[node]) {
        --in_degree[e.dst];
        if (in_degree[e.dst] == 0)
          q.push(e.dst);
      }
    }

    for (const auto& node : nodes)
      if (in_degree[node] != 0)
        return vector<T>();
    return result;
  }

  // dijkstra cost (pairs of node, distance to node)
  unordered_map<T, double> dijkstra_cst(const T& src) {
    unordered_set<T> vis;
    unordered_map<T, double> dist;
    priority_queue<pair<double, T>, vector<pair<double, T>>,
        greater<pair<double, T>>> pq;

    for (const auto& node : nodes)
      dist[node] = numeric_limits<double>::max();
    dist[src] = 0;
    pq.emplace(0, src);

    unordered_map<T, double> res;
    while (!pq.empty()) {
      auto p = pq.top();
      pq.pop();
      res[p.second] = p.first;

      auto node = p.second;
      if (vis.count(node))
        continue;
      vis.insert(node);

      for (const auto& e : adjlist[node]) {
        if (dist[node] + e.cost < dist[e.dst]) {
          dist[e.dst] = dist[node] + e.cost;
          pq.emplace(dist[e.dst], e.dst);
        }
      }
    }

    return res;
  }

private:
  unordered_set<T> nodes;
  unordered_map<T, vector<edge<T>>> adjlist;
};

// Test code
int main()
{
  freopen("dijkstra.in", "r", stdin);
  freopen("dijkstra.out", "w", stdout);

  int n, m;
  scanf("%d %d", &n, &m);
  digraph<int> g;
  for (int i = 1; i <= m; ++i) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    g.add_edge(a, b, c);
  }

  int INF = (int)(1e9 + 7);
  auto ma = g.dijkstra_cst(1);
  for (size_t i = 2; i <= n; ++i)
    printf("%d ", ma[i] > INF ? 0 : static_cast<int>(ma[i]));
  printf("\n");

  return 0;
}