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.

Examples

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


Output

4
5
4
3


Input

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


Output

1
2
2


Input

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


Output

194
194
97
90
149
66
149
140
129
129
194
111
129
194
140
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;
 
 
#define NUM 100005
 
struct Edge{
    Edge(int arg_to,ll arg_cost){
        to = arg_to;
        cost = arg_cost;
    }
    int to;
    ll cost;
};
 
vector<Edge> G[NUM]; //グラフの隣接リスト表現
int N; //ノードの個数
int root; //根ノードの番号
int MAX_LOG_V = 17;
int POW[18];
int parent[20][NUM];
int depth[NUM];
ll COST[NUM];
 
//parentとdepthを再帰的に設定
void dfs(int node_id,int parent_id,int d,ll sum_cost){
 
    parent[0][node_id] = parent_id;
    depth[node_id] = d;
    COST[node_id] = sum_cost;
 
    for(int i = 0; i < G[node_id].size(); i++){
        if(G[node_id][i].to != parent_id){
            dfs(G[node_id][i].to,node_id,d+1,sum_cost+G[node_id][i].cost);
        }
    }
}
 
//初期化
void init(){
    //parent[0]とdepthを初期化する
    dfs(root,-1,0,0);
    //parentを初期化する
    for(int k = 0; k + 1 < MAX_LOG_V; k++){
        for(int node_id = 0; node_id < N; node_id++){
            if(parent[k][node_id] < 0)parent[k+1][node_id] = -1; //node_idの2^k上のノードがルートノードより上なら、2^(k+1)上も同様とする
            else{
                parent[k+1][node_id] = parent[k][parent[k][node_id]];
            }
        }
    }
}
 
//leftとrightのLCAを求める
int lca(int left,int right){
    //leftとrightの深さが同じになるまで親を辿る
    if(depth[left] > depth[right])swap(left,right); //rightの方が深い所にいる
 
    for(int k = MAX_LOG_V-1; k >= 0; k--){
        if(depth[right]-depth[left] >= POW[k]){ //たとえば深さの差が39なら、32+4+2+1のように、ノードを上方に移動させる
            right = parent[k][right];
        }
    }
 
    if(left == right)return left;
 
    for(int k = MAX_LOG_V-1; k >= 0; k--){
        if(parent[k][left] == parent[k][right]){
            //Do nothing
        }else{
            left = parent[k][left];
            right = parent[k][right];
        }
    }
    return parent[0][left]; //最後は、leftの親とrightの親が必ず一致している
}
 
ll get_cost(int left,int right){
 
    int LCA = lca(left,right);
 
    return COST[left]+COST[right]-2*COST[LCA];
}
 
int get_node(int base_node,int diff){
 
    int ret = base_node;
 
    for(int loop = MAX_LOG_V-1; loop >= 0; loop--){
        if(diff & (1 << loop)){
            ret = parent[loop][ret];
        }
    }
    return ret;
}
 
ll calc_ans(int deeper,int LCA,ll DIST){
 
    int L = LCA,R = deeper,mid;
 
    ll ret = HUGE_NUM;
 
    ll cost_to_mid,REST;
 
    for(int loop = 0; loop < 20; loop++){
 
        mid = get_node(R,(depth[R]-depth[L])/2);
 
        cost_to_mid = COST[deeper]-COST[mid];
        REST = DIST-cost_to_mid;
 
        ret = min(ret,max(cost_to_mid,REST));
 
        if(cost_to_mid == REST){
 
            return ret;
 
        }else if(cost_to_mid < REST){
 
            R = parent[0][mid];
 
        }else{
 
            L = mid;
        }
    }
 
    return ret;
}
 
ll calc(int a,int b,int c){
 
    ll dist[3];
 
    dist[0] = get_cost(a,b);
    dist[1] = get_cost(a,c);
    dist[2] = get_cost(b,c);
 
    ll maximum = -HUGE_NUM;
    int index;
    for(int i = 0; i < 3; i++){
        if(maximum < dist[i]){
            maximum = dist[i];
            index = i;
        }
    }
 
    int left,right;
    ll DIST = maximum;
 
    switch(index){
    case 0:
        left = a;
        right = b;
        break;
    case 1:
        left = a;
        right = c;
        break;
    case 2:
        left = b;
        right = c;
        break;
    }
 
    int LCA = lca(left,right);
 
    ll cost_left = get_cost(left,LCA);
    ll cost_right = get_cost(right,LCA);
 
    if(cost_left == cost_right){
 
        return cost_left;
    }
 
    if(cost_left > cost_right){
 
        return calc_ans(left,LCA,DIST);
 
    }else{
 
        return calc_ans(right,LCA,DIST);
    }
}
 
int main(){
 
    for(int i = 0; i <= 17; i++)POW[i] = pow(2,i);
 
    int num_query;
 
    scanf("%d %d",&N,&num_query);
 
    int from,to;
    ll cost;
 
    for(int i = 0; i < N-1; i++){
 
        scanf("%d %d %lld",&from,&to,&cost);
        from--;
        to--;
        G[from].push_back(Edge(to,cost));
        G[to].push_back(Edge(from,cost));
    }
 
    root = 0;
    init();
 
    int a,b,c;
 
    for(int loop = 0; loop < num_query; loop++){
 
        scanf("%d %d %d",&a,&b,&c);
        a--;
        b--;
        c--;
 
        printf("%lld\n",calc(a,b,c));
    }
 
    return 0;
}
