import java.io.PrintWriter import java.util.* fun PrintWriter.solve() { val n = nextInt() val k = nextInt() val g = Array(n + k) { arrayListOf>() } repeat(n - 1) { val a = nextInt() - 1 val b = nextInt() - 1 val c = nextInt() g[a].add(Pair(b, c)) g[b].add(Pair(a, c)) } //LCA-begin val logn = 16 val dep = Array(n) { -1 } val dis = LongArray(n) { 0 } val nxt = Array(logn + 1) { Array(n) { -1 } } val que = ArrayDeque() dep[0] = 0 que.addLast(0) while (que.isNotEmpty()) { val cur = que.pollFirst() for ((to, cost) in g[cur]) { if (dep[to] == -1) { dep[to] = dep[cur] + 1 dis[to] = dis[cur] + cost nxt[0][to] = cur que.addLast(to) } } } for (j in 0 until logn) { for (i in 0 until n) { if (nxt[j][i] != -1) { nxt[j + 1][i] = nxt[j][nxt[j][i]] } } } fun lca(x: Int, y: Int): Int { var a = x var b = y if (dep[a] > dep[b]) { a = y b = x } val d = dep[b] - dep[a] for (j in logn downTo 0) { if (d and (1 shl j) > 0) b = nxt[j][b] } if (a == b) return a for (j in logn downTo 0) { if (nxt[j][a] != nxt[j][b]) { a = nxt[j][a] b = nxt[j][b] } } return nxt[0][a] } //LCA-end val p = Array(n) { 0 } for (i in 0 until k) { val m = nextInt() p[i] = nextInt() repeat(m) { val x = nextInt() - 1 g[n + i].add(Pair(x, 0)) g[x].add(Pair(n + i, p[i])) } } val q = nextInt() val ans = Array(q) { 0L } val u = Array(q) { 0 } val v = Array(q) { 0 } for (i in 0 until q) { u[i] = nextInt() - 1 v[i] = nextInt() - 1 ans[i] = dis[u[i]] + dis[v[i]] - 2 * dis[lca(u[i], v[i])] } //Dijkstra-begin val dp = Array(n + k) { 0L } val pq = PriorityQueue() for (i in 0 until k) { val yet = Array(n + k) { true } dp[n + i] = 0 yet[n + i] = false pq.add((n + i).toLong()) while (pq.isNotEmpty()) { var d = pq.remove() val cur = (d % (n + k)).toInt() d /= n + k if (dp[cur] < d) continue for ((to, cost) in g[cur]) { if (yet[to]) { yet[to] = false dp[to] = d + cost pq.add((d + cost) * (n + k) + to) } else if (dp[to] > d + cost) { dp[to] = d + cost pq.add((d + cost) * (n + k) + to) } } } for (j in 0 until q) { if (ans[j] > dp[u[j]] + dp[v[j]] + p[i]) { ans[j] = dp[u[j]] + dp[v[j]] + p[i] } } } //Dijkstra-end for (x in ans) println(x) } fun main() { val writer = PrintWriter(System.out, false) writer.solve() writer.flush() } // region Scanner private var st = StringTokenizer("") private val br = System.`in`.bufferedReader() fun next(): String { while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine()) return st.nextToken() } fun nextInt() = next().toInt() fun nextLong() = next().toLong() fun nextLine() = br.readLine()!! fun nextDouble() = next().toDouble() // endregion