#ifdef NACHIA #define _GLIBCXX_DEBUG #else // disable assert #define NDEBUG #endif #include #include #include #include using namespace std; using ll = long long; const ll INF = 1ll << 60; #define REP(i,n) for(ll i=0; i using V = vector; template void chmax(A& l, const B& r){ if(l < r) l = r; } template void chmin(A& l, const B& r){ if(r < l) l = r; } namespace nachia { struct DsuFast{ private: std::vector w; public: DsuFast(int n = 0) : w(n, -1) {} int leader(int u){ if(w[u] < 0) return u; return w[u] = leader(w[u]); } int operator[](int u){ return leader(u); } int merge(int u, int v){ u = leader(u); v = leader(v); if(u == v) return u; if(-w[u] < -w[v]) std::swap(u, v); w[u] += w[v]; w[v] = u; return u; } int size(int u){ return -w[leader(u)]; } bool same(int u, int v){ return leader(u) == leader(v); } int addElem(){ int res = int(w.size()); w.push_back(-1); return res; } }; } // namespace nachia void testcase(){ ll N, M, Q; cin >> N >> M >> Q; V S(N); REP(i,N) cin >> S[i]; ll dist_lim = *max_element(S.begin(), S.end()) * 2; V> edges; nachia::DsuFast dsu(N); ll edge_weight_lim = dist_lim; REP(i,M){ ll u,v,w; cin >> u >> v >> w; u--; v--; edge_weight_lim /= 2; if(w == 0){ dsu.merge(u, v); } else if(w <= edge_weight_lim){ edges.push_back({u,v,w<<(i+1)}); } } REP(i,N) chmin(S[dsu.leader(i)], S[i]); REP(i,N) chmin(S[i], S[dsu.leader(i)]); for(auto& [u,v,w] : edges){ u = dsu.leader(u); v = dsu.leader(v); } V X; for(auto [u,v,w] : edges) X.push_back(u); for(auto [u,v,w] : edges) X.push_back(v); sort(X.begin(), X.end()); X.erase(unique(X.begin(), X.end()), X.end()); auto xat = [&](ll x) -> ll { if(!binary_search(X.begin(), X.end(), x)) return -1ll; return lower_bound(X.begin(), X.end(), x) - X.begin(); }; ll K = X.size(); V> D(K, V(K, dist_lim)); REP(i,K) D[i][i] = 0; for(auto [u,v,w] : edges) chmin(D[xat(u)][xat(v)], w); REP(j,K) REP(i,K) REP(k,K) chmin(D[i][k], D[i][j] + D[j][k]); REP(k,edges.size()) for(auto [u,v,w] : edges){ chmin(S[v], S[u] + w); chmin(S[u], S[v] + w); } REP(qi,Q){ ll a, b; cin >> a >> b; a--; b--; ll ans = S[a] + S[b]; if(xat(a) >= 0 && xat(b) >= 0){ chmin(ans, D[xat(a)][xat(b)]); } cout << ans << "\n"; } } int main(){ cin.tie(0)->sync_with_stdio(0); testcase(); return 0; }