import std.conv, std.functional, std.range, std.stdio, std.string; import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons; import core.bitop; class EOFException : Throwable { this() { super("EOF"); } } string[] tokens; string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; } int readInt() { return readToken.to!int; } long readLong() { return readToken.to!long; } real readReal() { return readToken.to!real; } bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } } bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } } int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; } int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); } int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); } int N; int[] A, B; long[] C; int[][] G; int[] par, dep; long[] dist; void dfs(int u, int p, int ip) { par[u] = p; dep[u] = (p == -1) ? 0 : (dep[p] + 1); dist[u] = (p == -1) ? 0 : (dist[p] + C[ip]); foreach (i; G[u]) { const v = A[i] ^ B[i] ^ u; if (v != p) { dfs(v, u, i); } } } enum E = 17; enum INF = 10L^^18; struct Info { int last; long mn; long[2] xs; }; Info mul(in Info f, in Info g) { Info h; h.last = g.last; h.mn = min(f.mn, (g.xs[0] != dist[f.last] - dist[par[f.last]]) ? g.xs[0] : g.xs[1], g.mn); h.xs = f.xs; return h; } void main() { try { for (; ; ) { N = readInt(); A = new int[N - 1]; B = new int[N - 1]; C = new long[N - 1]; foreach (i; 0 .. N - 1) { A[i] = readInt() - 1; B[i] = readInt() - 1; C[i] = readLong(); } const Q = readInt(); auto X = new int[Q]; auto Y = new int[Q]; foreach (q; 0 .. Q) { X[q] = readInt() - 1; Y[q] = readInt() - 1; } G = new int[][N]; foreach (i; 0 .. N - 1) { G[A[i]] ~= i; G[B[i]] ~= i; } par = new int[N]; dep = new int[N]; dist = new long[N]; dfs(0, -1, -1); auto dd = new Info[][](E, N); foreach (u; 0 .. N) { dd[0][u].last = u; dd[0][u].mn = INF; dd[0][u].xs[] = INF; foreach (i; G[u]) { const v = A[i] ^ B[i] ^ u; if (v != par[u]) { long tmp = C[i]; foreach (k; 0 .. 2) { if (dd[0][u].xs[k] > tmp) { swap(dd[0][u].xs[k], tmp); } } } } } foreach (e; 0 .. E - 1) { foreach (u; 0 .. N) { const l = dd[e][u].last; if (l == -1 || par[l] == -1) { dd[e + 1][u] = dd[e][u]; } else { dd[e + 1][u] = mul(dd[e][u], dd[e][par[l]]); } } } debug { foreach (e; 0 .. E - 1) { writefln("dd[%s] = %s", e, dd[e]); } } auto mns = new long[][](N, 3); foreach (u; 0 .. N) { mns[u][] = INF; foreach (i; G[u]) { long tmp = C[i]; foreach (k; 0 .. 3) { if (mns[u][k] > tmp) { swap(mns[u][k], tmp); } } } } debug { auto d = new long[][](N, N); foreach (u; 0 .. N) { d[u][] = INF; d[u][u] = 0; } foreach (i; 0 .. N - 1) { chmin(d[A[i]][B[i]], C[i]); chmin(d[B[i]][A[i]], C[i]); } foreach (w; 0 .. N) foreach (u; 0 .. N) foreach (v; 0 .. N) { chmin(d[u][v], d[u][w] + d[w][v]); } } foreach (q; 0 .. Q) { int u = X[q], v = Y[q]; if (dep[u] > dep[v]) { swap(u, v); } debug { writefln("dep[%s] = %s, dep[%s] = %s", u, dep[u], v, dep[v]); } int lca; long ans = INF; Info fu, fv; fu.last = fv.last = -2; foreach_reverse (e; 0 .. E) { if (dep[u] <= dep[v] - (1 << e)) { debug { writefln("%s -> %s", v, par[dd[e][v].last]); } fv = (fv.last == -2) ? dd[e][v] : mul(fv, dd[e][v]); v = par[dd[e][v].last]; } } if (u == v) { debug { writeln("u == v"); writeln("fv = ", fv); } lca = u; chmin(ans, (mns[u][0] != dist[fv.last] - dist[u]) ? mns[u][0] : mns[u][1]); chmin(ans, fv.mn); chmin(ans, fv.xs[0]); } else { foreach_reverse (e; 0 .. E) { if (dep[u] - (1 << e) >= 0 && par[dd[e][u].last] != par[dd[e][v].last]) { debug { writefln("%s -> %s, %s -> %s", u, par[dd[e][u].last], v, par[dd[e][v].last]); } fu = (fu.last == -2) ? dd[e][u] : mul(fu, dd[e][u]); fv = (fv.last == -2) ? dd[e][v] : mul(fv, dd[e][v]); u = par[dd[e][u].last]; v = par[dd[e][v].last]; } } debug { writeln("lca = ", lca); writeln("fu = ", fu); writeln("fv = ", fv); } lca = par[u]; fu = (fu.last == -2) ? dd[0][u] : mul(fu, dd[0][u]); fv = (fv.last == -2) ? dd[0][v] : mul(fv, dd[0][v]); long[2] tmps = [dist[u] - dist[lca], dist[v] - dist[lca]]; if (tmps[0] > tmps[1]) { swap(tmps[0], tmps[1]); } chmin(ans, (mns[lca][0] != tmps[0]) ? mns[lca][0] : (mns[lca][1] != tmps[1]) ? mns[lca][1] : mns[lca][2]); chmin(ans, fu.mn); chmin(ans, fu.xs[0]); chmin(ans, fv.mn); chmin(ans, fv.xs[0]); } debug { writeln("lca = ", lca, ", ans = ", ans); } debug { long brt = INF; foreach (i; 0 .. N - 1) { if (d[X[q]][Y[q]] == d[X[q]][A[i]] + C[i] + d[B[i]][Y[q]] || d[X[q]][Y[q]] == d[X[q]][B[i]] + C[i] + d[A[i]][Y[q]]) { // edge on the path } else if (d[X[q]][Y[q]] == d[X[q]][A[i]] + d[A[i]][Y[q]] || d[X[q]][Y[q]] == d[X[q]][B[i]] + d[B[i]][Y[q]]) { chmin(brt, C[i]); } } assert(brt == ans, format("query %s %s: %s %s", X[q], Y[q], brt, ans)); assert(d[X[q]][Y[q]] == dist[X[q]] + dist[Y[q]] - 2 * dist[lca]); } if (ans >= INF) { writeln(-1); } else { ans *= 2; ans += dist[X[q]] + dist[Y[q]] - 2 * dist[lca]; writeln(ans); } } } } catch (EOFException e) { } }