#include <bits/stdc++.h>
#include <climits>
#define int long long
using namespace std;
constexpr int MOD = 1000000007;
 
// ! std::array does NOT initialize its elements. use std::vector when possible!!!
// cand ai de-a face cu cautari binare, ia-ti cateva minute si analizeaza ce vrei
//  cautarea binara sa returneze pentru anumite valori ca sa-ti dai seama ce functie
//  sa folosesti
// la probleme de astea precum 1926/E o idee este sa iei un set de elemente si sa rezolvi
//  recursiv setul ramas
 
vector<pair<int, int>> adj[100010];
int n;
 
int costs[100010], visited[100010];
inline void dijkstra() {
  fill(costs, costs + n + 1, LONG_MAX >> 2);
  priority_queue<pair<int, int>> pq; // <node, - (MINUS) cost used to reach that node>
 
  costs[1] = 0;
  pq.emplace(0, 1);
 
  while (!pq.empty()) {
    auto [cost, node] = pq.top(); pq.pop();
    if (visited[node]) continue;
    cost = -cost;
    costs[node] = cost;
 
    // if we reached this line it means we can safely say
    // that we know the smallest cost to reach `node`
    visited[node] = 1;
 
    for (auto [neigh, tax] : adj[node]) {
      // we want to add as few nodes as possible into pq
      // beacause inserting is expensive; thus, we only add
      // a node if we know that we can improve its cost
      if (cost + tax < costs[neigh]) {
        costs[neigh] = cost + tax;
        pq.emplace(-costs[neigh], neigh);
      }
    }
  }
}
 
int32_t main() {
#ifndef N257
  freopen("dijkstra.in", "r", stdin);
  freopen("dijkstra.out", "w", stdout);
#endif
  cin.tie(0)->sync_with_stdio(0);
 
  int m; cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v, c; cin >> u >> v >> c;
    adj[u].emplace_back(v, c);
  }
 
  dijkstra();
 
  for (int i = 1; i <= n; i++)
    cout << costs[i] << ' ' ;
}