#pragma GCC optimize("O3") #include using namespace std; using ll=long long; typedef pair P; #define fi first #define se second #define all(v) (v).begin(),(v).end() const ll inf=(1e18); const ll mod=1000000007; //ios_base::sync_with_stdio(false); //cin.tie(NULL); ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;} struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout< bool chmax(T &a, const T &b) { if (a bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; } vector fare; template struct DLCA{ const int Log; vector dep; vector cost; const G &g; vector> table; explicit DLCA(const G &g):g(g),dep(g.size()),Log(32-__builtin_clz(g.size())){ table.assign(Log,vector(g.size(),-1)); cost.assign(g.size(),0); } //各点に番号付 void dfs(int idx,int par,int d){ table[0][idx]=par; dep[idx]=d; if(par!=-1)cost[idx]+=cost[par]+fare[idx]; else cost[idx]+=fare[idx]; for(auto &to:g[idx]){ if(to!=par)dfs(to,idx,d+1); } } //構築 void build(){ dfs(0,-1,0); for(int k=0;kdep[v])swap(u,v); for(int i=Log-1;i>=0;i--){ if(dep[v]-dep[u]&(1<=0;i--){ if(table[i][u]!=table[i][v]){ u=table[i][u]; v=table[i][v]; } } return table[0][u]; } //2点間距離 int dist(int u,int v){ int par=query(u,v); return abs(dep[u]-dep[par])+abs(dep[v]-dep[par]); } ll money(int u,int v){ int par=query(u,v); return cost[u]+cost[v]-2*cost[par]+fare[par]; } }; int main(){ int n; cin>>n; vector> graph(n); for(int i=0;i>a>>b; graph[a].push_back(b); graph[b].push_back(a); } fare.resize(n); for(int i=0;i>fare[i]; } DLCA>>lca(graph); lca.build(); int q;cin>>q; ll ans=0; while(q--){ ll a,b,c; cin>>a>>b>>c; ans+=(lca.money(a,b))*c; } cout<