#include <bits/stdc++.h>

using namespace std;

using Edge = pair<int, int>;
using Graph = vector<vector<Edge>>;

vector<int> dijkstra(const Graph &graph, int source){
  const int N = (int)graph.size();

  using Node = pair<int, int>;

  auto cmp = [](Node L, Node R){
    return L.second > R.second;
  };

  priority_queue<Node, vector<Node>, decltype(cmp)> min_heap(cmp);
  vector<int> dist(N, -1);

  min_heap.push({0, 0});
  dist[source] = 0;

  while (!min_heap.empty()){
    Node node = min_heap.top();
    min_heap.pop();

    int u = node.first;
    int d = node.second;

    if (dist[u] != d)
      continue;

    for (auto edge: graph[u]){
      int v = edge.first;
      int w = edge.second;

      if (dist[v] == -1 || dist[v] > dist[u] + w){
        dist[v] = dist[u] + w;
        min_heap.push({v, dist[v]});
      }
    }
  }

  auto it = find(dist.begin(), dist.end(), 0);
  dist.erase(it);

  return dist;
}

int main(){
  ifstream cin("dijkstra.in");
  ofstream cout("dijkstra.out");

  ios_base::sync_with_stdio(false);

  int N, M;
  cin >> N >> M;

  Graph graph(N);

  for (int i = 0; i < M; i++){
    int u, v, w;
    cin >> u >> v >> w;
    u--; v--;

    graph[u].push_back({v, w});
  }

  auto dists = dijkstra(graph, 0);

  for (int x: dists)
    cout << x << " ";
  cout << endl;

  return 0;
}