1024 - 待ち合わせ

問題文

あなたはヅイア王国にあるイアヅ高校の教員である。ヅイア王国にはN 個の都市とN-1 本の街道が存在し、どの都市からどの都市へもいくつかの街道を通って移動することができる。各街道は双方向に移動可能で、その長さもわかっている。

あなたは授業の一環として次のような課題を計画している。まず、相異なる３つの都市に共通するテーマをいくつか用意する。次に、各テーマに対し３人のグループを割り当てる。割り当てられたグループは３つの都市について１人ずつ担当を決め、各都市で現地調査を行う。その後、N 個の都市のうちのどこかに集合し、成果をまとめる。

各テーマについて、３人はそれぞれの調査対象の都市から集合先の都市まで最短距離で移動する。３人の移動距離のうち、最も長い距離をそのテーマのコストとする。あなたは、テーマごとのコストが最小になるように集合先の都市を選びたい。

課題

都市の個数、街道の情報、テーマごとに指定された3つの都市がQ個与えられたとき、テーマごとのコストの最小値を求めるプログラムを作成せよ。

入力・出力

入力

入力は以下の形式で与えられる。

N Q
u1 v1 w1
u2 v2 w2
:
uN-1 vN-1 wN-1
a1 b1 c1
a2 b2 c2
:
aQ bQ cQ

1行目に、ヅイア王国の都市の数N(3≦N≦100,000)、テーマの個数Q(1≦Q≦100,000)が与えられる。続くN-1行に、i番目の街道の情報を表すu_i, v_i, w_i(1≦u_i < v_i ≦N, 1≦w_i≦10,000)が、すべて整数で与えられる。これはi番目の街道をが都市u_iと都市v_iを結んでおり、その長さはw_iであることを表している。続くQ行にi番目のテーマの調査対象の都市の番号a_i, b_i, c_i(1≦a_i < b_i < c_i≦N)が与えられる。

出力

各テーマに対して、コストの最小値を1行に出力する。

入出力例

入力例 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

出力例 1

4
5
4
3

1つめのテーマでは都市2に集合すると都市3に居る生徒の移動距離である4がコストとなる。
コストを4未満にできるような集合先の都市は存在しないので、4を出力する。
2つめのテーマでは、都市2または都市4に集合するとコストが5になり、これが最小である。

入力例 2

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

出力例 2

1
2
2

入力例 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

出力例 3

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