#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using namespace atcoder; typedef long long ll; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define repr(i, n) for (int i = (int)(n) - 1; i >= 0; i--) #define repk(i, k, n) for (int i = k; i < (int)(n); i++) #define all(v) v.begin(), v.end() #define mod1 1000000007 #define mod2 998244353 #define mod3 100000007 #define vi vector #define vs vector #define vc vector #define vl vector #define vb vector #define vvi vector> #define vvc vector> #define vvl vector> #define vvb vector> #define vvvi vector>> #define vvvl vector>> #define pii pair #define pil pair #define pli pair #define pll pair #define vpii vector> #define vpll vector> #define vvpii vector>> #define vvpll vector>> template void debug(T e) { cerr << e << endl; } template void debug(vector &v) { rep(i, v.size()) { cerr << v[i] << " "; } cerr << endl; } template void debug(vector> &v) { rep(i, v.size()) { rep(j, v[i].size()) { cerr << v[i][j] << " "; } cerr << endl; } } template void debug(vector> &v) { rep(i, v.size()) { cerr << v[i].first << " " << v[i].second << endl; } } template void debug(set &st) { for (auto itr = st.begin(); itr != st.end(); itr++) { cerr << *itr << " "; } cerr << endl; } template void debug(multiset &ms) { for (auto itr = ms.begin(); itr != ms.end(); itr++) { cerr << *itr << " "; } cerr << endl; } template void debug(map &mp) { for (auto itr = mp.begin(); itr != mp.end(); itr++) { cerr << itr->first << " " << itr->second << endl; } } void debug_out() { cerr << endl; } template void debug_out(Head H, Tail... T) { cerr << H << " "; debug_out(T...); } using mint = modint998244353; void debug_mint1(vector &vec) { for (int i = 0; i < vec.size(); i++) { cerr << vec[i].val() << " "; } cerr << endl; } void debug_mint2(vector> &vec) { for (int i = 0; i < vec.size(); i++) { for (int j = 0; j < vec[i].size(); j++) { cerr << vec[i][j].val() << " "; } cerr << endl; } } pll op(pll a, pll b) { return min(a, b); } pll e() { return pll(100000000, -1); } struct LCA { // LCA を解くライブラリ. vector> graph; vector euler_tour; vector dist; vector intime; vector outtime; segtree, op, e> seg; ll NN; LCA(ll N, vector &u, vector &v) { NN = N; vector emp(0); for (int i = 0; i < N; i++) { graph.push_back(emp); } euler_tour.resize(0); dist.assign(N, N + 2); intime.assign(N, -1); outtime.assign(N, -1); seg = segtree, op, e>(2 * N - 1); for (ll i = 0; i < N - 1; i++) { graph[u[i]].push_back(v[i]); graph[v[i]].push_back(u[i]); } } void out_graph() { for (ll i = 0; i < NN; i++) { for (ll j = 0; j < graph[i].size(); j++) { cout << graph[i][j] << " "; } cout << endl; } } void dfs(vector &isvisited, ll v) { isvisited[v] = true; for (ll x : graph[v]) { if (isvisited[x]) { continue; } euler_tour.push_back(v); dfs(isvisited, x); } euler_tour.push_back(v); } void make_euler_tour() { vector isvisited(NN, false); dfs(isvisited, 0); } void prepare() { make_euler_tour(); // BFS をして距離を求める queue que; que.push(0); dist[0] = 0; while (que.size()) { ll p = que.front(); que.pop(); for (ll x : graph[p]) { if (dist[x] < NN) { continue; } dist[x] = dist[p] + 1; que.push(x); } } // セグメント木に,どのタイミングで入ったかの情報(そして頂点番号も!)を記録しておく for (ll i = 0; i < 2 * NN - 1; i++) { seg.set(i, pair(dist[euler_tour[i]], i)); } // 入るタイミング,出るタイミングを記録したテーブルを用意する for (ll i = 0; i < 2 * NN - 1; i++) { if (intime[euler_tour[i]] == -1) { intime[euler_tour[i]] = i; } } for (ll i = 2 * NN - 2; i >= 0; i--) { if (outtime[euler_tour[i]] == -1) { outtime[euler_tour[i]] = i; } } } ll lca_query(ll a, ll b) { if (intime[a] > outtime[b]) { swap(a, b); } pair p = seg.prod(intime[a], outtime[b] + 1); return euler_tour[p.second]; } ll lca_dist(ll a, ll b) { ll da = dist[a]; ll db = dist[b]; ll dab = dist[lca_query(a, b)]; return da + db - 2 * dab; } ll make_auxiliary_tree(vector &v_list, vector &v_list_after, vector> &graph) { // 頂点のリスト v_list を渡す // 実際に使う頂点のリストは v_list_after に、グラフは graph にある // 返り値は根の頂点番号とする vector p(0); for (ll i = 0; i < v_list.size(); i++) { p.push_back(pll(intime[v_list[i]], v_list[i])); } sort(all(p)); for (ll i = 0; i < v_list.size() - 1; i++) { ll lca = lca_query(p[i].second, p[i + 1].second); p.push_back(pll(intime[lca], lca)); } sort(all(p)); p.erase(unique(p.begin(), p.end()), p.end()); // debug(p); ll len = p.size(); graph.resize(len); stack st; st.push(0); v_list_after.push_back(p[0].second); for (ll i = 1; i < len; i++) { while (true) { ll tp = st.top(); if (outtime[p[tp].second] >= intime[p[i].second]) { break; } st.pop(); } ll tp = st.top(); graph[tp].push_back(i); graph[i].push_back(tp); st.push(i); v_list_after.push_back(p[i].second); } return p[0].second; } }; void dfs(vector &et, vector &intime, vector &outtime, vector> &graph, vector &isvisited, ll v){ isvisited[v] = true; intime[v] = et.size(); et.push_back(v); for (ll x: graph[v]){ if (isvisited[x]) continue; dfs(et, intime, outtime, graph, isvisited, x); } outtime[v] = et.size(); et.push_back(v); return; } int main() { ll T; cin >> T; while (T--){ ll N, M; cin >> N >> M; vector A(N); rep(i, N) cin >> A[i]; vector u(M); vector v(M); rep(i, M){ cin >> u[i] >> v[i]; u[i]--; v[i]--; } // 最大全域木問題に帰着できる? vector> ps; rep(i, M){ ps.push_back(make_pair(A[u[i]] + A[v[i]], make_pair(u[i], v[i]))); } rep(i, N){ ps.push_back(make_pair(A[i], make_pair(i, N))); } dsu tree(N + 1); ll ans = 0; sort(all(ps)); reverse(all(ps)); for (ll i = 0; i < ps.size(); i++){ ll cost = ps[i].first; pll ed = ps[i].second; if (!tree.same(ed.first, ed.second)){ tree.merge(ed.first, ed.second); ans += cost; } } rep(i, N){ ans -= A[i]; } cout << ans << endl; } }