#include <iostream> #include <vector> #include <algorithm> #include <set> #include <map> #include <fstream> #include <queue> #define rep(i, s, e) for (ll i = s; i < e; i++) #define upmax(a, b) a = max(a, b) #define upmin(a, b) a = min(a, b) using namespace std; using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using pll = pair<ll, ll>; using vpll = vector<pll>; using vvpll = vector<vpll>; const ll INF = 1e18; const ll MASK_SZ = 32; vvpll g; vvll dist; ll get_mask(ll p1, ll p2, ll p3, ll p4, ll p5) { ll mask = 0; if (p1 != -1) mask += 1; if (p2 != -1) mask += 2; if (p3 != -1) mask += 4; if (p4 != -1) mask += 8; if (p5 != -1) mask += 16; return mask; } void dijkstra(ll startNode) { priority_queue<pair<ll, pll>, vector<pair<ll, pll>>, greater<pair<ll, pll>>> pq; // {dist, {node, mask}} dist[startNode][0] = 0; pq.push({ 0, {startNode, 0} }); while (!pq.empty()) { ll node = pq.top().second.first; ll curDist = pq.top().first; ll mask = pq.top().second.second; //cout << "node = " << node << " curDist = " << curDist << " mask = " << mask << endl; pq.pop(); // Use no ticket: for (auto& it : g[node]) { ll nei = it.first, w = it.second; if (w + dist[node][mask] < dist[nei][mask]) { dist[nei][mask] = w + dist[node][mask]; pq.push({ dist[nei][mask], {nei, mask} }); } } ll num_ticket = 1; for (ll bit = 1; bit < 32; bit *= 2) { if ((bit & mask) == 0) { // This bit is 0 in mask - we did not use this ticket yet for (auto& it : g[node]) { ll nei = it.first, w = it.second; w *= (10 - num_ticket); w /= 10; if (w + dist[node][mask] < dist[nei][mask + bit]) { dist[nei][mask + bit] = w + dist[node][mask]; pq.push({ dist[nei][mask + bit], {nei, mask + bit} }); } } } num_ticket++; } } } ll price(ll mask, ll p1, ll p2, ll p3, ll p4, ll p5) { ll ans = 0; if (mask & (ll)1) ans += p1; if (mask & (ll)2) ans += p2; if (mask & (ll)4) ans += p3; if (mask & (ll)8) ans += p4; if (mask & (ll)16) ans += p5; return ans; } void solve() { ll n, m, k; cin >> n >> m >> k; g.clear(), g.resize(n + 1); dist.clear(), dist.resize(n + 1, vll(MASK_SZ, INF)); vll t(k); rep(i, 0, k) { cin >> t[i]; g[n].push_back({ t[i], 0 }); } rep(i, 0, m) { ll a, b, c; cin >> a >> b >> c; g[b].push_back({ a, c }); } dijkstra(n); ll q; cin >> q; while (q--) { ll start, p1, p2, p3, p4, p5; cin >> start >> p1 >> p2 >> p3 >> p4 >> p5; ll mask = get_mask(p1, p2, p3, p4, p5); ll ans = INF; rep(i, 0, MASK_SZ) { //if (dist[start][i & mask] == INF) continue; upmin(ans, dist[start][i & mask] + price(i & mask, p1, p2, p3, p4, p5)); } if (ans == INF) cout << -1 << endl; else cout << ans << endl; } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); solve(); }