#include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N,M,Q; cin >> N >> M >> Q; vector S(N); for(auto &s : S) cin >> s; vector P; vector> edge; for(int i=0; i> u >> v >> w,u--,v--; if(i > 62) continue; for(int k=0; k<=i; k++){ w += w; if(w >= S.at(u)+S.at(v)) break; } if(w >= S.at(u)+S.at(v)) continue; P.push_back(u),P.push_back(v); edge.push_back({u,v,w}); } sort(P.begin(),P.end()); P.erase((unique(P.begin(),P.end())),P.end()); int n = P.size(); vector> dist(n,vector(n)); for(int i=0; i> a >> b,a--,b--; int pa = lower_bound(P.begin(),P.end(),a)-P.begin(); int pb = lower_bound(P.begin(),P.end(),b)-P.begin(); if(P.at(pa) != a && P.at(pb) != b){ cout << S.at(a)+S.at(b) << "\n"; continue; } if(P.at(pb) == b) swap(a,b),swap(pa,pb); if(P.at(pb) == b){ cout << dist.at(pa).at(pb) << "\n"; continue; } else{ long long answer = S.at(a)+S.at(b); for(int i=0; i