012 - 待ち合わせ

時間制限 8 秒 / メモリ制限 256 MB / 得点 12 / x 0 /


TLE
8sec
MLE
256MB
得点
12

問題文

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

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

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

課題

都市の個数、街道の情報、テーマごとに指定された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番目の街道の情報を表すui, vi, wi(1≦ui < vi ≦N, 1≦wi≦10,000)が、すべて整数で与えられる。これはi番目の街道をが都市uiと都市viを結んでおり、その長さはwiであることを表している。続くQ行にi番目のテーマの調査対象の都市の番号ai, bi, ci(1≦ai < bi < ci≦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