#include using namespace std; using ll =long long; #define all(v) v.begin(),v.end() #define rep(i,a,b) for(int i=a;i=b;i--) ll INF=2e18; struct LCA { ll V; ll logV; vector> G; ll root; vector> parent;//いないなら-1 vector depth; //コンストラクタ LCA(ll V_) :V(V_) { root=0; ll k=1; logV=0; while(k<=V) { k*=2; logV++; } G=vector> (V,vector (0)); parent=vector> (V,vector (logV,-1)); depth=vector (V); } void dfs(ll v,ll p,ll d) { parent[v][0]=p; depth[v]=d; for(ll i=0;idepth[v]) swap(u,v); for(ll k=0;k>k)&1) { v=parent[v][k]; } } if(u==v) return u; for(ll k=logV-1;k>=0;k--) { if(parent[u][k]!=parent[v][k]) { u=parent[u][k]; v=parent[v][k]; } } return parent[u][0]; } }; int main() { ll N;cin>>N; LCA p(N); for(ll i=0;i>a>>b; p.G[a].push_back(b); p.G[b].push_back(a); } p.init(); vector U(N); for(ll i=0;i>U[i]; vector d(N,INF); queue> S; S.push({0,0}); while(!S.empty()) { auto x=S.front(); S.pop(); if(d[x.first]!=INF) continue; d[x.first]=x.second+U[x.first]; for(auto y:p.G[x.first]) { S.push({y,d[x.first]}); } } ll M;cin>>M; ll ans=0; for(ll i=0;i>A>>B>>C; ll k=p.lca(A,B); ll count=d[A]+d[B]-2*d[k]+U[k]; ans+=count*C; } cout<