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"
#define rep(i, n)       for (i64 i = 0, i##_limit = (n); i < i##_limit; ++i)

using namespace std;
using i64 = int_fast64_t;
template<class T, class U>inline bool chmax(T &a, const U &b){return b>a && (a=b, true);}
template<class T, class U>inline bool chmin(T &a, const U &b){return b<a && (a=b, true);}
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

struct Edge { // {{{
    int src, to;
    int64_t cost = 0;

    inline Edge(int src,  int to, const int64_t &cost) noexcept :
        src(src), to(to), cost(cost) {}

    inline Edge(int to, const int64_t &cost) noexcept :
        src(-1), to(to), cost(cost) {}

    inline Edge() noexcept {}

    bool operator< (const Edge &o) const noexcept { return cost < o.cost; }
    bool operator> (const Edge &o) const noexcept { return o < *this; }

    Edge& operator=(int to) noexcept {
        this->to = to;
        return *this;
    }

    operator int() const noexcept { return to; }
};
// }}}
using WeightedGraph     = vector<vector<Edge>>;
using UnWeightedGraph   = vector<vector<int>>;

class HeavyLightDecomposition { // {{{
public:
    WeightedGraph G;            // 重み付きグラフ
    const int V;                // ノード数
    vector<int> parent;         // 親
    vector<int> treeSize;       // 自分も含めた部分木のサイズ
    vector<int> head;           // HL分解後の自分が属するグループ(チェイン)の先頭ノード
    vector<int> vid;            // 根からDFSしたときにそのノードを訪れた順番
    vector<int> nodeOfVid;      // vidからノードを逆算する用
    vector<int64_t> weightSum;  // 根からのコストの総和
    vector<int> depth;          // 根からの深さ(経由するエッジの数)

    HeavyLightDecomposition() = delete;

    // 空の木を構築する。管理できるノードは [0, V) なので注意。
    explicit HeavyLightDecomposition(int V) :
        G(V), V(V),
        parent(V, -1), treeSize(V), head(V),
        vid(V), nodeOfVid(V),
        weightSum(V, 0),
        depth(V, 0) {}


    // u-v間に無向辺を張る。重みは省略可
    inline void addEdge(int u, int v, int64_t weight = 1) {
        G[u].emplace_back(u, v, weight);
        G[v].emplace_back(v, u, weight);
    }

    // HL分解、その他もろもろ前計算
    void build(int root = 0) {
        int timestamp = 0;
        head[root] = root;
        dfs_treeSize(root);
        dfs_HLDecomp(root, timestamp);
    }

    // u,v の最小共通祖先を求める
    int lca(int u, int v) const {
        while(head[u] != head[v]) {
            if (vid[u] > vid[v]) swap(u, v);
            v = parent[head[v]];
        }
        return (vid[u] < vid[v]) ? u : v;
    }

    // 根に向かって v から k だけ登ったノードを求める
    int climb(int v, int k) const {
        while(1) {
            const int h = head[v];
            if (vid[v] - k >= vid[h]) return nodeOfVid[vid[v] - k];
            k -= vid[v] - vid[h] + 1;
            v = parent[h];
        }
    }

    // u-v間のパスの重みの和を求める
    int64_t pathWeight(int u, int v) const {
        return weightSum[u] + weightSum[v] - (2 * weightSum[lca(u, v)]);
    }

    // u-v間のパスの「エッジの個数」を求める
    int pathCountEdge(int u, int v) const {
        return depth[u] + depth[v] - (2 * depth[lca(u, v)]);
    }

private: // {{{

    // treeSize[v], parent[v], depth[v], weightSum[v] を再帰によって計算
    // v の子の中で最もheavyなやつを G[v] の先頭にもってくる
    int dfs_treeSize(int v) {
        treeSize[v] = 1;
        if (!G[v].empty() && G[v].front().to == parent[v]) swap(G[v].front(), G[v].back());
        for (auto &e : G[v]) {
            if (e.to == parent[v]) continue;
            parent[e.to] = v;
            depth[e.to] = depth[v] + 1;
            weightSum[e.to] = weightSum[v] + e.cost;
            treeSize[v] += dfs_treeSize(e.to);
            if (treeSize[e.to] > treeSize[G[v].front()]) swap(e, G[v].front());
        }
        return treeSize[v];
    }

    // G[v] の先頭に v の子中で最もheavyなノードがある前提でHL分解し、
    // vid[v], nodeOfVid[v], head[v] を求める
    void dfs_HLDecomp(int v, int &timestamp) {
        vid[v] = timestamp;
        nodeOfVid[timestamp] = v;
        ++timestamp;
        for (const int to : G[v]) {
            if (to == parent[v]) continue;
            head[to] = (to == G[v].front() ? head[v] : to);
            dfs_HLDecomp(to, timestamp);
        }
    } // }}}
}; // }}}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    HeavyLightDecomposition G(N+1);

    rep(i, N - 1) {
        int u, v, w;
        cin >> u >> v >> w;
        G.addEdge(u, v, w);
    }

    // 根のノードを1としてHL分解
    G.build(1);

    // a-b, a-c, b-c の3つのパスの中で重みが最大のものを探し、
    // { パスの始点, パスの終点 } のペアを返す。
    const auto maxWeightPath = [&G](int a, int b, int c) -> pair<int,int> {
        const auto weightAB = G.pathWeight(a, b);
        const auto weightAC = G.pathWeight(a, c);
        const auto weightBC = G.pathWeight(b, c);
        const auto maxv = max({ weightAB, weightAC, weightBC });
        if (maxv == weightAB) return { a, b };
        if (maxv == weightAC) return { a, c };
        return { b, c };
    };

    // s からlcaに向かって登る距離を [low, high) で2分探索
    // (パス[s-lca]上で、weight(s, p) < weight(t, p) を満たし、s からできるだけ離れたノードを探索)
    // 探索途中のノードも解の候補に含めるので逐次 res を更新する
    const auto binSearch = [&G](int s, int lca, int t) -> i64 {
        i64 res = LINF;
        int low = 0;
        int high = G.pathCountEdge(s, lca) + 1;
        while(high - low > 1) {
            const int mid = (low + high) / 2;
            const int p = G.climb(s, mid);
            const auto weightSP = G.pathWeight(s, p);
            const auto weightTP = G.pathWeight(t, p);
            chmin(res, max(weightSP, weightTP));
            if (weightSP < weightTP) {
                low = mid;
            } else {
                high = mid;
            }
        }
        const int p = G.climb(s, low);
        chmin(res, max(G.pathWeight(s, p), G.pathWeight(t, p)));
        return res;
    };

    const auto solve = [&](int a, int b, int c) -> i64 {
        int s, t;
        tie(s, t) = maxWeightPath(a, b, c);
        const int lca = G.lca(s, t);
        return min(binSearch(s, lca, t), binSearch(t, lca, s));
    };

    rep(i, Q) {
        int a, b, c;
        cin >> a >> b >> c;
        cout << solve(a, b, c) << "\n";
    }

    return 0;
}


