import java.io.*; import java.util.*; @SuppressWarnings("unused") public class Main { FastScanner in; PrintWriter out; final static int MOD = (int)1e9+7; void solve(){ int N = in.nextInt(); ArrayList> g = new ArrayList<>(); for(int i = 0; i < N; i++) g.add(new ArrayList<>()); for(int i = 0; i < N - 1; i++){ int u = in.nextInt(), v = in.nextInt(); long cost = in.nextLong(); g.get(u).add(new Edge(u, v, cost)); g.get(v).add(new Edge(v, u, cost)); } long[] sum = new long[N]; boolean[] visited = new boolean[N]; ArrayDeque queue = new ArrayDeque(); visited[0] = true; queue.addLast(0); while(!queue.isEmpty()){ int v = queue.removeFirst(); for(Edge edge : g.get(v)){ int to = edge.to; long cost = edge.cost; if(visited[to]) continue; visited[to] = true; sum[to] = sum[v] + cost; queue.addLast(to); } } LowestCommonAncestor lca = new LowestCommonAncestor(g, 0); int Q = in.nextInt(); for(int i = 0; i < Q; i++){ int x = in.nextInt(), y = in.nextInt(), z = in.nextInt(); long ans = 0; ans += sum[x] + sum[y] - 2 * sum[lca.getLCA(x, y)]; ans += sum[y] + sum[z] - 2 * sum[lca.getLCA(y, z)]; ans += sum[z] + sum[x] - 2 * sum[lca.getLCA(z, x)]; ans /= 2; out.println(ans); } } class Edge implements Comparable{ int from; int to; long cost; public Edge(int f, int t, long c){ from = f; to = t; cost = c; } @Override public int compareTo(Edge o) { return Long.compare(this.cost, o.cost); } } class LowestCommonAncestor { int[] vs, depth, id; ArrayList> T; SparseTableIndex sti; //Euler-Tour Technique public LowestCommonAncestor(ArrayList> T, int root){ vs = new int[T.size()*2-1]; depth = new int[T.size()*2-1]; id = new int[T.size()]; this.T = T; dfsStack(root); sti = new SparseTableIndex(depth); } void dfsStack(int root){ ArrayDeque stack = new ArrayDeque<>(); int k = 0; stack.addLast(new int[]{0, root, -1, 0}); while(!stack.isEmpty()){ int[] node = stack.removeLast(); int v = node[1], p = node[2], d = node[3]; if(node[0] == 0){ id[v] = k; vs[k] = v; depth[k] = d; k++; for(Edge edge : T.get(v)) { if (edge.to == p) continue; stack.addLast(new int[]{1, v, p, d}); stack.addLast(new int[]{0, edge.to, v, d+1}); } }else{ vs[k] = v; depth[k] = d; k++; } } } public int getLCA(int u, int v){ int L = Math.min(id[u], id[v]), R = Math.max(id[u], id[v]); return vs[sti.get(L, R+1)]; } class SparseTableIndex { int[][] table; int[] height; int[] v; public SparseTableIndex(int[] v){ init(v); } void init(int[] v){ this.v = Arrays.copyOf(v, v.length); int n = v.length, h = 0; while((1<>1]+1; for(int i = 0; i < n; i++) table[0][i] = i; for(int i = 1; i < h; i++) { for (int j = 0; j < n; j++) { int x = table[i - 1][j], y = table[i - 1][Math.min(j + (1 << (i - 1)), n - 1)]; table[i][j] = v[x] <= v[y] ? x : y; } } } public int get(int a, int b){ int l = height[b-a]; int x = table[l][a], y = table[l][b-(1<