#include #include using namespace std; class UnionFind{ private: vector par,siz; public: UnionFind(int N){ par.resize(N,-1); siz.resize(N,1); } int root(int x){ //連結成分の代表頂点を返す. if(par.at(x) == -1) return x; else return par.at(x) = root(par.at(x)); } bool unite(int u, int v){ //u,vを連結する 連結してた->false,した->trueを返す. u = root(u),v = root(v); if(u == v) return false; if(siz.at(u) < siz.at(v)) swap(u,v); //Union by size. par.at(v) = u; siz.at(u) += siz.at(v); return true; } bool issame(int u, int v){ //同じ連結成分ならtrue. if(root(u) == root(v)) return true; else return false; } int size(int pos){return siz.at(root(pos));} //posの連結成分の大きさを返す. }; 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; UnionFind Z(N); for(int i=0; i> u >> v >> w,u--,v--; if(w == 0){ Z.unite(u,v); 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; edge.push_back({u,v,w}); } for(int i=0; i> dist(n,vector(n)); for(int i=0; i> a >> b,a--,b--; a = Z.root(a),b = Z.root(b); if(a == b){cout << "0\n"; continue;} 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