πριο

#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<int> vi;
vector<vi> AdjList1;
vi visited;
vi taken;
vector<vii> AdjList;
priority_queue< ii, vector<ii>, greater<ii> > pq;
int e=0;
#define INF 1e5
void update(int edge) {
taken[edge] = 1;
for (int j = 0; j < AdjList[edge].size(); j++) {
ii v = AdjList[edge][j];
if (taken[v.first]==0)
pq.push(ii(v.second, v.first));
}
}
void bfs(long long s){

visited[s] = 1;

queue<long long> q;

q.push(s);

while (!q.empty()) {

long long u = q.front();

q.pop();

e++;

for (long long j = 0; j < AdjList1[u].size(); j++) {

long long v = AdjList1[u][j];

if (visited[v] == 0){

visited[v] = 1;

q.push(v);

}

}

}

}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    for(int k=0;k<t;k++){
        int V, a, b, w;
        long long E;
        cin >> V >> E;
        map<int,bool>m;
        int s;
        bool q1=0;
        vector<int>qw;
        taken.assign(V, 0);
        AdjList.assign(V, vii());
        AdjList1.assign(V, vi());
        for(int i=0;i<V;i++){
            cin>>m[i];
            if(m[i] == 1){
                s=i;
                q1= 1;
                for(int j=0;j<qw.size();j++){
                    AdjList[i].push_back(ii(qw[j],0));
                    AdjList[qw[j]].push_back(ii(i,0));
                }
                qw.push_back(s);
            }
        }
        visited.assign(V, 0);
        for (long long i = 0; i < E; i++) {
            cin >> a >> b >> w;
            if(m[a-1] != 1 || m[b-1] != 1){
                AdjList[a-1].push_back(ii(b-1, w));
                AdjList[b-1].push_back(ii(a-1, w));
            }
            AdjList1[a-1].push_back(b-1);
            AdjList1[b-1].push_back(a-1);
        }
        e=0;
        bfs(0);
        if(e != V || q1 == 0){
            cout<<"impossible"<<endl;
        }
        else{
        int cost = 0;
                update(s);
                while (!pq.empty()){
                    ii front = pq.top();
                    pq.pop();
                    int w = front.first;
                    int u = front.second;
                    if (taken[u]==0){
                        cost += w;
                    }
                    update(u);
                }
        cout<<cost<<endl;
    }
    }
return 0;
}