Teleportation Solution

#include <bits/stdc++.h>
using namespace std;
//Credits: cw_42(Aviansh)
void solve() {
    int n,m;
    cin >> n>> m;
    int a[n];
    for(int &i : a) cin >> i;
    vector<pair<int,int>> g[n];
    for(int i = 0; i < m;i++){ //add edges in our graph
        int a,b,d;
        cin >> a >> b >> d;
        g[a].push_back({b,d});
        g[b].push_back({a,d});
    }
    
    int k;
    cin >> k;
    while(k--){ //process all queries
        set<pair<int,array<int,2>>> pq; //{cost, {node, fuel}}
        int c,s,e;
        cin >> c >> s >> e;
        map<array<int,2>,int> vis; //map 1: vis[{node, fuel}]: min cost such that {cost, [node, fuel}} is visited & processed
        map<array<int,2>,int> he; //map 2: he[{node, fuel}]: min cost such that {cost, [node, fuel}} is visited
        pq.insert({0, {s , 0}}); //at src with 0 cost and 0 fuel
        int ans = -1; //impossible initally
        while(!pq.empty()) {
            pair<int,array<int,2>> p = *pq.begin();
            pq.erase(pq.begin()); //take best option (greedy)
            if(vis.find(p.second) != vis.end()) continue; //we have come here before
            vis[p.second] = p.first; //we have come here now, processing
            if(p.second[0] == e){ //path found!
                ans = p.first;
                break;
            }
            for(pair<int,int> e : g[p.second[0]]) { //visit neighbours
                if(p.second[1] >= e.second){ //we can visit this edge with current fuel
                    if(he.find({e.first,p.second[1] - e.second}) != he.end()) //this node has been visited
                        if(he[{e.first,p.second[1] - e.second}] < p.first) //with lower cost?
                            continue; //no use in visiting it now
                        else //remove it from the set, we have found a better way!
                            pq.erase({he[{e.first,p.second[1] - e.second}],{e.first,p.second[1] - e.second}});
                    pq.insert({p.first,{e.first,p.second[1] - e.second}}); //add the current path to set
                    he[{e.first,p.second[1] - e.second}] = p.first; //its been visited!
                }
            }
            if(p.second[1] < c) { //refuel at current spot
                p.second[1]++; //1 unit fuel added
                p.first += a[p.second[0]]; //add to our cost
                pq.insert(p); //insert this state
            }
        }
        
        if(ans == -1) { //no path found
            cout << "impossible\n";
            continue;
        }
        cout << ans << "\n"; //print answer
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--)
        solve();
    return 0;
}