#include <algorithm> #include <iostream> #include <numeric> #include <tuple> #include <unordered_map> #include <utility> #include <vector> using namespace std; using i64 = long long; struct DSU { vector<int> fa, siz; DSU(int n) : fa(n + 1) , siz(n + 1, 1) { iota(fa.begin(), fa.end(), 0); } int leader(int u) { while (u != fa[u]) u = fa[u] = fa[fa[u]]; return u; } void merge(int u, int v) { u = leader(u); v = leader(v); if (u == v) return; else if (siz[u] < siz[v]) swap(u, v); siz[u] += siz[v]; fa[v] = u; } bool same(int u, int v) { return leader(u) == leader(v); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, m; cin >> n >> m; vector<int> a(n + 1); for (int i = 1; i <= n; ++i) cin >> a[i]; vector<tuple<int, int, int>> edges(m); unordered_map<int, unordered_map<int, int>> len; for (auto& edge : edges) { auto &u = get<0>(edge), &v = get<1>(edge), &w = get<2>(edge); cin >> u >> v >> w; len[u][v] = len[v][u] = w; } int cur = 0; vector<int> order(n); iota(order.begin(), order.end(), 1); sort(order.begin(), order.end(), [&](int u, int v) { return a[u] < a[v]; }); sort(edges.begin(), edges.end(), [](const auto& lhs, const auto& rhs) { return get<2>(lhs) < get<2>(rhs); }); DSU uf(n); i64 ans = 0; int rem = n - 1; for (auto i : order) { while (rem > 0 && cur < m) { int u = get<0>(edges[cur]), v = get<1>(edges[cur]), w = get<2>(edges[cur]); if (w > a[i]) break; if (uf.same(u, v)) { ++cur; continue; } uf.merge(u, v); ans += w; ++cur; --rem; } if (rem == 0) break; for (int j = 1; rem > 0 && j <= n; ++j) { if (len[i][j] != 0 || uf.same(i, j)) continue; uf.merge(i, j); ans += a[i]; --rem; } } while (rem > 0 && cur < m) { int u = get<0>(edges[cur]), v = get<1>(edges[cur]), w = get<2>(edges[cur]); if (uf.same(u, v)) { ++cur; continue; } uf.merge(u, v); ans += w; ++cur; --rem; } cout << ans << endl; return 0; }