#include using namespace std; using lint = long long; template using V = vector; template using VV = V< V >; struct Edge { int to, cost; }; template pair< V, V > dijkstra(const VV& g, int s = 0) { V dist(g.size(), numeric_limits::max()); using P = pair; priority_queue< P, V

, greater

> pque; pque.emplace(dist[s] = 0, s); while (!pque.empty()) { T d; int v; tie(d, v) = pque.top(); pque.pop(); if (d > dist[v]) continue; for (const auto& e : g[v]) if (dist[v] + e.cost < dist[e.to]) { pque.emplace(dist[e.to] = dist[v] + e.cost, e.to); } } V dp(g.size(), 1e18); dp[s] = 0; for (int v = 0; v < g.size(); ++v) { for (const auto& e : g[v]) { dp[e.to] = min({dp[e.to], dp[v] + e.cost, dist[v], dist[e.to]}); } } return {dist, dp}; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n, m; cin >> n >> m; VV g(n); while (m--) { int a, b, c; cin >> a >> b >> c, --a, --b; g[a].emplace_back(Edge{b, c}); g[b].emplace_back(Edge{a, c}); } auto p = dijkstra(g); for (int i = 0; i < n; ++i) { cout << p.first[i] + p.second[i] << '\n'; } }