あなたはヅイア王国にあるイアヅ高校の教員である。ヅイア王国には$N$個の都市と$N-1$本の街道が存在し、どの都市からどの都市へもいくつかの街道を通って移動することができる。各街道は双方向に移動可能で、その長さもわかっている。
あなたは授業の一環として次のような課題を計画している。まず、相異なる３つの都市に共通するテーマをいくつか用意する。次に、各テーマに対し３人のグループを割り当てる。割り当てられたグループは３つの都市について１人ずつ担当を決め、各都市で現地調査を行う。その後、$N$個の都市のうちのどこかに集合し、成果をまとめる。
各テーマについて、３人はそれぞれの調査対象の都市から集合先の都市まで最短距離で移動する。３人の移動距離のうち、最も長い距離をそのテーマのコストとする。あなたは、テーマごとのコストが最小になるように集合先の都市を選びたい。
都市の個数、街道の情報、テーマごとに指定された３つの都市が$Q$個与えられたとき、テーマごとのコストの最小値を求めるプログラムを作成せよ。
入力は以下の形式で与えられる。
$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$
１行目に、ヅイア王国の都市の数$N$ ($3 \leq N \leq 100,000$)、テーマの個数$Q$ ($1 \leq Q \leq 100,000$)が与えられる。続く$N-1$行に、$i$番目の街道の情報を表す$u_i,v_i,w_i$ ($ 1 \leq u_i < v_i \leq N, 1 \leq w_i \leq 10,000$)が、すべて整数で与えられる。これは$i$番目の街道が都市$u_i$と都市$v_i$を結んでおり、その長さは$w_i$であることを表している。続く$Q$行に$i$番目のテーマの調査対象の都市の番号$a_i,b_i,c_i$ ($1 \leq a_i < b_i < c_i \leq N$) が与えられる。
各テーマに対して、コストの最小値を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
4 5 4 3
1つめのテーマでは、都市2に集合すると都市3に居る生徒の移動距離である4がコストとなる。コストを4未満にできるような集合先の都市は存在しないので、4を出力する。2つめのテーマでは、都市2または都市4に集合するとコストが5になり、これが最小である。
5 3 1 2 1 2 3 1 3 4 1 4 5 1 1 2 3 1 3 5 1 2 4
1 2 2
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
194 194 97 90 149 66 149 140 129 129 194 111 129 194 140