#include #define fi first #define se second #define rep(i,s,n) for (int i = (s); i < (n); ++i) #define rrep(i,g,n) for (int i = (n)-1; i >= (g); --i) #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define len(x) (int)(x).size() #define dup(x,y) (((x)+(y)-1)/(y)) #define pb push_back #define eb emplace_back #define Field(T) vector> using namespace std; using ll = long long; using ull = unsigned long long; template using pq = priority_queue,greater>; using P = pair; templatebool chmax(T&a,T b){if(abool chmin(T&a,T b){if(b par; vector siz; UnionFind(int sz_): n(sz_), cnt(sz_), par(sz_), siz(sz_, 1) { for (int i = 0; i < sz_; ++i) par[i] = i; } void init(int sz_) { n = sz_, cnt = sz_; par.resize(sz_); siz.assign(sz_, 1); for (int i = 0; i < sz_; ++i) par[i] = i; } int root(int x) { if (par[x] == x) { return x; } else { int r = root(par[x]); return par[x] = r; } } bool merge(int x, int y) { x = root(x); y = root(y); if (x == y) return false; if (siz[x] < siz[y]) swap(x, y); siz[x] += siz[y]; par[y] = x; --cnt; return true; } bool is_same(int x, int y) { return root(x) == root(y); } int size(int x) { return siz[root(x)]; } int group_cnt() { return cnt; } vector> groups() { vector> ret(n); for (int i = 0; i < n; ++i) { ret[root(i)].emplace_back(i); } ret.erase(remove_if(ret.begin(), ret.end(), [](const vector &v) { return v.empty(); }), ret.end()); return ret; } }; int main() { int n, m, q; cin >> n >> m >> q; vector s(n); rep(i,0,n) cin >> s[i]; vector u(m), v(m); vector w(m); UnionFind uf(n); rep(i,0,m) { cin >> u[i] >> v[i] >> w[i]; --u[i], --v[i]; if (w[i] == 0) uf.merge(u[i], v[i]); } vector> gs = uf.groups(); vector ids(n); int l = len(gs); rep(i,0,l) { for (int v : gs[i]) ids[v] = i; } vector ns(l, 2000000000000000000); rep(i,0,n) { chmin(ns[ids[i]], s[i]); } rep(i,0,m) { u[i] = ids[u[i]], v[i] = ids[v[i]]; } n = l; s = ns; vector> G(n); rep(i,0,m) if (u[i] != v[i]) { if (w[i] > 0 && i < 60 && w[i] <= ((2000000000000000100)>>(i+1))) { G[u[i]].eb(v[i], w[i]<<(i+1)); G[v[i]].eb(u[i], w[i]<<(i+1)); } } // vector dist(n, 0); // rep(i,0,n) { // dist[i] = s[i]; // que.emplace(s[i], i); // } // while(!que.empty()) { // auto [c, v] = que.top(); // que.pop(); // if (dist[v] < c) continue; // for (auto [nv, cost] : G[v]) { // if (dist[nv] > dist[v]+cost) { // dist[nv] = dist[v]+cost; // que.emplace(dist[nv], nv); // } // } // } pq

que; vector> mp(n); rep(s,0,n) { que.emplace(0, s); mp[s][s] = 0; while(!que.empty()) { auto [c, v] = que.top(); que.pop(); if (mp[s][v] < c) continue; for (auto [nv, cost] : G[v]) if (c+cost <= 3000000000000000000) { if (!mp[s].contains(nv) || mp[s][nv] > c+cost) { mp[s][nv] = c+cost; que.emplace(c+cost, nv); } } } } while(q--) { int a, b; cin >> a >> b; --a, --b; a = ids[a], b = ids[b]; if (a == b) { cout << 0 << endl; continue; } ll ans = s[a]+s[b]; for (auto [v1, c1] : mp[a]) for (auto [v2, c2] : mp[b]) { if (v1 == v2) { chmin(ans, c1+c2); } else { chmin(ans, c1+c2+s[v1]+s[v2]); } } cout << ans << endl; } return 0; }