#include using namespace std; using ll = long long; template T MUL(T a, T b){ T res; return __builtin_mul_overflow(a, b, &res)? std::numeric_limits::max() : res; } int main(){ constexpr ll inf = 1ll << 61; ios::sync_with_stdio(false); cin.tie(0); int n, m, q; cin >> n >> m >> q; vector s(n); for(auto &&v : s) cin >> v; m = min(m, 61); vector> E(m); vector V; for(int i = 0; i < m; i++){ auto &&[u, v, w] = E[i]; cin >> u >> v >> w; u--, v--; V.emplace_back(u); V.emplace_back(v); w = min(MUL(w, 1ll << (i + 1)), inf); } sort(V.begin(), V.end()); V.erase(unique(V.begin(), V.end()), V.end()); int vn = V.size(); vector> A(vn, vector(vn, inf)); for(int i = 0; i < m; i++){ auto [u, v, w] = E[i]; u = lower_bound(V.begin(), V.end(), u) - V.begin(); v = lower_bound(V.begin(), V.end(), v) - V.begin(); A[v][u] = A[u][v] = min(A[u][v], w); } for(int i = 0; i < vn; i++) A[i][i] = 0; for(int i = 0; i < vn; i++){ for(int j = 0; j < vn; j++){ A[i][j] = min(A[i][j], s[V[i]] + s[V[j]]); } } for(int k = 0; k < vn; k++){ for(int i = 0; i < vn; i++){ for(int j = 0; j < vn; j++){ A[i][j] = min(A[i][j], A[i][k] + A[k][j]); } } } while(q--){ int a, b; cin >> a >> b; a--, b--; ll ans = s[a] + s[b]; int u = lower_bound(V.begin(), V.end(), a) - V.begin(); int v = lower_bound(V.begin(), V.end(), b) - V.begin(); if(u < vn && V[u] == a && v < vn && V[v] == b){ for(int i = 0; i < vn; i++){ for(int j = 0; j < vn; j++){ ans = min(ans, A[u][i] + A[i][j] + A[j][v]); } } } cout << ans << '\n'; } }