UVA 11367

#include <bits/stdc++.h>

using namespace std;

struct PqEdge{
    int d,fuel,v;
     bool operator<(const PqEdge &b) const{
        return d > b.d;
    }
};

int main(){
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);

    int n,m;
    cin >> n >> m;

    struct Edge{
        int v,c;
    };
    vector<vector<Edge>> g(n);
    vector<int> p(n);

    for(int i = 0; i < n; ++i)
        cin >> p[i];

    while(m-->0){
        int x,y,c;
        cin >> x >> y >> c;
        g[x].push_back({y,c});
        g[y].push_back({x,c});
    }

    int q;
    cin >> q;
    while(q--){
        int c,s,e;
        cin >> c >> s >> e;

        vector<vector<int>> d(n, vector<int>(c+1, ~(1<<31)));
        priority_queue<PqEdge, vector<PqEdge>> pq;
        pq.push({0,0,s});
        d[s][0] = 0;

        while(!pq.empty()){
            auto edge = pq.top();pq.pop();
            if(edge.d > d[edge.v][edge.fuel]) continue;

            for(auto E : g[edge.v]){
                if(edge.fuel >= E.c){
                    if(d[edge.v][edge.fuel] < d[E.v][edge.fuel - E.c]){
                        d[E.v][edge.fuel - E.c] = d[edge.v][edge.fuel];
                        pq.push({d[E.v][edge.fuel - E.c], edge.fuel - E.c, E.v});
                    }
                }
            }

            if(edge.fuel + 1 <= c){
                if(d[edge.v][edge.fuel] + p[edge.v] < d[edge.v][edge.fuel+1]){
                    d[edge.v][edge.fuel + 1] = d[edge.v][edge.fuel] + p[edge.v];
                    pq.push({d[edge.v][edge.fuel + 1], edge.fuel + 1, edge.v});
                }
            }
        }

        int min = ~(1<<31);
        for(int f = 0; f <= c; ++f){
            min = std::min(d[e][f], min);
        }

        if(min == ~(1<<31)) cout << "impossible" << endl;
        else cout << min << endl;
    }

    return 0;

}