#include <iostream> #include <queue> #include <utility> #include <vector> using namespace std; using i64 = long long; int N; vector<vector<pair<int, int>>> graph; vector<i64> dist; void solve() { priority_queue<pair<i64, int>> nodes; for (int i = 1; i <= N; ++i) nodes.emplace(-dist[i], i); while (!nodes.empty()) { const auto& cur = nodes.top(); i64 dis = -cur.first; int u = cur.second; nodes.pop(); if (dis != dist[u]) continue; for (const auto& node : graph[u]) { int v = node.first, w = node.second; if (dist[v] > dis + w) { dist[v] = dis + w; nodes.emplace(-dist[v], v); } } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int M; cin >> N >> M; dist.resize(N + 1); for (int i = 1; i <= N; ++i) { cin >> dist[i]; dist[i] = -dist[i]; } graph.resize(N + 1); for (int i = 0; i < M; ++i) { int a, b, c; cin >> a >> b >> c; graph[a].emplace_back(b, c); graph[b].emplace_back(a, c); } solve(); for (int i = 1; i <= N; ++i) cout << -dist[i] << '\n'; return 0; }