Problem:

Meeting in a City

　

  You are a teacher at Iazu High School is the Zuia Kingdom. There are $N$ cities and $N-1$ roads connecting them that allow you to move from one city to another by way of more than one road. Each of the roads allows bidirectional traffic and has a known length.
  

As a part of class activities, you are planning the following action assignment for your students. First, you come up with several themes commonly applicable to three different cities. Second, you assign each of the themes to a group of three students. Then, each student of a group is assigned to one of the three cities and conducts a survey on it. Finally, all students of the group get together in one of the $N$ cities and compile their results.
  

  After a theme group has completed its survey, the three members move from the city on which they studied to the city for getting together. The longest distance they have to travel for getting together is defined as the cost of the theme. You want to select the meeting city so that the cost for each theme becomes minimum.

  Given the number of cities, road information and $Q$ sets of three cities for each theme, make a program to work out the minimum cost for each theme.

Input

The input is given in the following format.

$N$ $Q$ 
$u_1$ $v_1$ $w_1$
$u_2$ $v_2$ $w_2$
$...$
$u_{N-1}$ $v_{N-1}$ $w_{N-1}$
$a_1$ $b_1$ $c_1$
$a_2$ $b_2$ $c_2$
$...$
$a_Q$ $b_Q$ $c_Q$

The first line provides the number of cities in the Zuia Kingdom $N$ ($3 \leq N \leq 100,000$) and the number of themes $Q$ ($1 \leq Q \leq 100,000$). Each of the subsequent $N-1$ lines provides the information regarding the $i$-th road $u_i,v_i,w_i$ ($ 1 \leq u_i < v_i \leq N, 1 \leq w_i \leq 10,000$), indicating that the road connects cities $u_i$ and $v_i$, and the road distance between the two is $w_i$. Each of the $Q$ lines that follows the above provides the three cities assigned to the $i$-th theme: $a_i,b_i,c_i$ ($1 \leq a_i < b_i < c_i \leq N$).
																																																																				   

Output

  For each theme, output the cost in one line.
 

Sample Input 1

5 4
1 2 3
2 3 4
2 4 2
4 5 3
1 3 4
1 4 5
1 2 3
2 4 5

Sample Output 1

4
5
4
3

In the first theme, traveling distance from City 3 (the student conducts survey) to City 2 (meeting venue) determines the cost 4. As no other meeting city can provide smaller cost, you should output 4. In the second theme, you can minimize the cost down to 5 by selecting City 2 or City 4 as the meeting venue.
  
  

Sample Input 2

5 3
1 2 1
2 3 1
3 4 1
4 5 1
1 2 3
1 3 5
1 2 4

Sample Output 2

1
2
2

Sample Input 3

15 15
1 2 45
2 3 81
1 4 29
1 5 2
5 6 25
4 7 84
7 8 56
4 9 2
4 10 37
7 11 39
1 12 11
11 13 6
3 14 68
2 15 16
10 13 14
13 14 15
2 14 15
7 12 15
10 14 15
9 10 15
9 14 15
8 13 15
5 6 13
11 13 15
12 13 14
2 3 10
5 13 15
10 11 14
6 8 11

Sample Output 3

194
194
97
90
149
66
149
140
129
129
194
111
129
194
140



Sample input:
5 4
1 2 3
2 3 4
2 4 2
4 5 3
1 3 4
1 4 5
1 2 3
2 4 5


Sample output:
4
5
4
3

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
def main():
  n, q = map(int, input().split())
  edges = [[] for _ in range(n)]
  for _ in range(n - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    edges[u].append((v, w))
    edges[v].append((u, w))
  
  height = [None] * n
  dist = [None] * n
  parent = [[None] * 20 for _ in range(n)]
  stack = [(0, 0, 0)]
  while stack:
    x, h, d = stack.pop()
    height[x] = h
    dist[x] = d
    for to, w in edges[x]:
      if height[to] == None:
        parent[to][0] = x
        stack.append((to, h + 1, d + w))
  for j in range(1, 20):
    for i in range(1, n):
      if height[i] >= 2 ** j:
        parent[i][j] = parent[parent[i][j - 1]][j - 1]
  
  def adj_height(x, n):
    if n == 0:
      return x
    acc = 1
    for i in range(20):
      if acc > n:
        return adj_height(parent[x][i - 1], n - acc // 2)
      acc *= 2
  
  def _lca(x, y):
    if x == y:
      return x
    for i in range(1 ,20):
      if parent[x][i] == parent[y][i]:
        return _lca(parent[x][i - 1], parent[y][i - 1])
  
  def lca(x, y):
    diff = height[x] - height[y]
    if diff < 0:
      y = adj_height(y, -diff)
    elif diff > 0:
      x = adj_height(x, diff)
    return _lca(x, y)
  
  def bs(index, target):
    if index == 0:
      return 0
    if dist[index] >= target >= dist[parent[index][0]]:
      return index
    for i in range(1, 20):
      if parent[index][i] == None or dist[parent[index][i]] <= target:
        return bs(parent[index][i - 1], target)
  
  def max_dist(x, y, z, r):
    xr = lca(x, r)
    yr = lca(y, r)
    zr = lca(z, r)
    return max(dist[x] + dist[r] - dist[xr] * 2, 
               dist[y] + dist[r] - dist[yr] * 2,
               dist[z] + dist[r] - dist[zr] * 2)
  
  def _score(x, y, z, xy, yz):
    dist_x = dist[x]
    dist_y = dist[y]
    dist_z = dist[z]
    dist_xy = dist[xy]
    dist_yz = dist[yz]
    dx = dist_x + dist_yz - dist_xy * 2
    dy = dist_y - dist_yz
    dz = dist_z - dist_yz
    if dx >= dy >= dz:
      if dist_x >= dist_y:
        r = bs(x, dist_xy + (dist_x - dist_y) / 2)
        if r == 0:
          return dist_x
        return min(max(dist_x - dist[r], dist_y + dist[r] - dist_xy * 2), 
                   max(dist_x - dist[parent[r][0]], dist_y + dist[parent[r][0]] - dist_xy * 2))
      else:
        r = bs(yz, dist_xy + (dist_y - dist_x) / 2)
        if r == 0:
          return dist_y
        return min(max(dist_y - dist[r], dist_x + dist[r] - dist_xy * 2), 
                   max(dist_y - dist[parent[r][0]], dist_x + dist[parent[r][0]] - dist_xy * 2))
  
    elif dx >= dz >= dy:
      if dist_x >= dist_z:
        r = bs(x, dist_xy + (dist_x - dist_z) / 2)
        if r == 0:
          return dist_x
        return min(max(dist_x - dist[r], dist_z + dist[r] - dist_xy * 2), 
                   max(dist_x - dist[parent[r][0]], dist_z + dist[parent[r][0]] - dist_xy * 2))
      else:
        r = bs(yz, dist_xy + (dist_z - dist_x) / 2)
        if r == 0:
          return dist_z
        return min(max(dist_z - dist[r], dist_x + dist[r] - dist_xy * 2), 
                   max(dist_z - dist[parent[r][0]], dist_x + dist[parent[r][0]] - dist_xy * 2))
 
    elif dy >= dx >= dz:
      r = bs(y, dist_yz + (dy - dx) / 2)
      if r == 0:
        return dist_y
      return min(max(dist_y - dist[r], dist_x + dist[r] - dist_xy * 2), 
                 max(dist_y - dist[parent[r][0]], dist_x + dist[parent[r][0]] - dist_xy * 2))
 
    elif dy >= dz >= dx:
      r = bs(y, dist_yz + (dy - dz) / 2)
      if r == 0:
        return dist_y
      return min(max(dist_y - dist[r], dist_z + dist[r] - dist_yz * 2), 
                 max(dist_y - dist[parent[r][0]], dist_z + dist[parent[r][0]] - dist_yz * 2))
 
    elif dz >= dx >= dy:
      r = bs(z, dist_yz + (dz - dx) / 2)
      if r == 0:
        return dist_z
      return min(max(dist_z - dist[r], dist_x + dist[r] - dist_xy * 2), 
                 max(dist_z - dist[parent[r][0]], dist_x + dist[parent[r][0]] - dist_xy * 2))
 
    elif dz >= dy >= dx:
      r = bs(z, dist_yz + (dz - dy) / 2)
      if r == 0:
        return dist_z
      return min(max(dist_z - dist[r], dist_y + dist[r] - dist_yz * 2), 
                 max(dist_z - dist[parent[r][0]], dist_y + dist[parent[r][0]] - dist_yz * 2))
  
  def score(a, b, c):
    a -= 1
    b -= 1
    c -= 1
    ab = lca(a, b)
    ac = lca(a, c)
    bc = lca(b, c)
    if ab == ac:
      return _score(a, b, c, ab, bc)
    elif ab == bc:
      return _score(b, a, c, ab, ac)
    else:
      return _score(c, a, b, ac, ab)
  
  for _ in range(q):
    a, b, c = map(int, input().split())
    print(score(a, b, c))

main()