#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>

using namespace std;
#define PB push_back
#define LL long long
#define int LL
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORD(i,a,b) for (int i = (a); i >= (b); i--)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define st first
#define nd second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define VI vector<int>
#define PII pair<int,int>
#define LD long double

struct fast_hash {
    size_t operator()(int x) const {
        x = ((x >> 16) ^ x) * 0x45d9f3b;
        x = ((x >> 16) ^ x) * 0x45d9f3b;
        x = (x >> 16) ^ x;
        return x;
    }
    size_t operator()(const void* p) const {
        return operator()((int)(intptr_t)p);
    }
};
template<class K, class V>
struct HashMap : unordered_map<K, V, fast_hash> {
    HashMap() { this->max_load_factor(0.25); }
};
struct HashSet : unordered_set<int, fast_hash> {
    HashSet() { this->max_load_factor(0.25); }
};

template<class C> void mini(C& a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C& a4, C b4) { a4 = max(a4, b4); }

template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

template<class T> ostream &operator<<(ostream &os, vector<T> V){
  os<<"[";for(auto vv:V)os<<vv<<",";return os<<"]";
}

template<class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";}
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<"="<<h<<","; _dbg(sdbg+1, a...);
}


#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

template<typename T>
struct MaxSeg {
    int n, sz;
    T id;
    vector<T> t;
    MaxSeg() : n(0), sz(0) {}
    MaxSeg(int n, T id) : n(n), id(id) {
        sz = 1;
        while (sz < n) sz <<= 1;
        t.assign(2 * sz, id);
    }
    MaxSeg(const vector<T>& a, T id) : n(SZ(a)), id(id) {
        sz = 1;
        while (sz < n) sz <<= 1;
        t.assign(2 * sz, id);
        REP(i, n) t[sz + i] = a[i];
        FORD(i, sz - 1, 1) t[i] = max(t[2*i], t[2*i+1]);
    }
    void update(int i, T val) {
        t[i + sz] = val;
        for (int v = (i + sz) >> 1; v >= 1; v >>= 1)
            t[v] = max(t[2*v], t[2*v+1]);
    }
    T query(int l, int r) const {
        T res = id;
        for (l += sz, r += sz + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = max(res, t[l++]);
            if (r & 1) res = max(res, t[--r]);
        }
        return res;
    }
    int find_first(int l, int r, T val) const {
        if (l > r || l >= n || r < 0) return -1;
        r = min(r, n - 1);
        return _find_first(1, 0, sz - 1, l, r, val);
    }
    int find_last(int l, int r, T val) const {
        if (l > r || l >= n || r < 0) return -1;
        r = min(r, n - 1);
        return _find_last(1, 0, sz - 1, l, r, val);
    }
private:
    int _find_first(int v, int tl, int tr, int l, int r, T val) const {
        if (tl > r || tr < l || t[v] < val) return -1;
        if (tl == tr) return tl;
        int tm = (tl + tr) / 2;
        int res = _find_first(2 * v, tl, tm, l, r, val);
        if (res != -1) return res;
        return _find_first(2 * v + 1, tm + 1, tr, l, r, val);
    }
    int _find_last(int v, int tl, int tr, int l, int r, T val) const {
        if (tl > r || tr < l || t[v] < val) return -1;
        if (tl == tr) return tl;
        int tm = (tl + tr) / 2;
        int res = _find_last(2 * v + 1, tm + 1, tr, l, r, val);
        if (res != -1) return res;
        return _find_last(2 * v, tl, tm, l, r, val);
    }
};

struct PairSeg {
    int n, sz;
    struct Node { int mf, mg, mfg; };
    vector<Node> t;
    static Node EMPTY() { return {(int)-1e18, (int)-1e18, (int)-1e18}; }
    static Node merge(const Node& a, const Node& b) {
        return {max(a.mf, b.mf), max(a.mg, b.mg),
                max({a.mfg, b.mfg, a.mf + b.mg})};
    }
    PairSeg() : n(0), sz(0) {}
    PairSeg(const VI& f, const VI& g) : n(SZ(f)) {
        sz = 1;
        while (sz < n) sz <<= 1;
        t.assign(2 * sz, EMPTY());
        REP(i, n) t[sz + i] = {f[i], g[i], (int)-1e18};
        FORD(i, sz - 1, 1) t[i] = merge(t[2*i], t[2*i+1]);
    }
    int query(int l, int r) const {
        if (l > r || l >= n || r < 0) return (int)-1e18;
        r = min(r, n - 1);
        return _query(1, 0, sz - 1, l, r).mfg;
    }
private:
    Node _query(int v, int tl, int tr, int l, int r) const {
        if (tl > r || tr < l) return EMPTY();
        if (l <= tl && tr <= r) return t[v];
        int tm = (tl + tr) / 2;
        return merge(_query(2*v, tl, tm, l, r),
                     _query(2*v+1, tm+1, tr, l, r));
    }
};

struct Graph {
    int n;
    vector<vector<PII>> adj; // neighbor, weight
    Graph() : n(0) {}
    Graph(int n) : n(n), adj(n) {}
    void add_edge(int u, int v, int w) {
        adj[u].PB({v, w});
        adj[v].PB({u, w});
    }
};

struct SubGraph {
    int root;
    int max_depth = 0;
    HashMap<int, vector<PII>> adj;
    void add_edge(int u, int v, int w) {
        adj[u].PB({v, w});
        adj[v].PB({u, w});
    }
    void compute_max_depth() {
        if (adj.empty()) {
            max_depth = 0;
            return;
        }
        HashMap<int, int> dist;
        dist.reserve(SZ(adj) + 1);
        vector<int> q = {root};
        dist[root] = 0;
        max_depth = 0;
        for (int qi = 0; qi < SZ(q); qi++) {
            int v = q[qi];
            for (auto [u, w] : adj[v]) {
                if (!dist.count(u)) {
                    dist[u] = dist[v] + w;
                    maxi(max_depth, dist[u]);
                    q.PB(u);
                }
            }
        }
    }

    mutable optional<pair<Graph, int>> _cached_graph;
    mutable int _cached_diam = -1;

    pair<Graph, int> to_graph() const {
        if (_cached_graph) return *_cached_graph;
        HashMap<int, int> id;
        id.reserve(SZ(adj) + 1);
        int cnt = 0;
        for (auto& [v, _] : adj) id[v] = cnt++;
        if (!id.count(root)) id[root] = cnt++;
        Graph g(cnt);
        for (auto& [v, es] : adj) {
            for (auto [u, w] : es) {
                if (v < u) g.add_edge(id[v], id[u], w);
            }
        }
        _cached_graph = {g, id[root]};
        return *_cached_graph;
    }

    int get_diam() const;
};

struct Diameter {
    int length;
    VI nodes;
    VI edges;
    vector<vector<SubGraph>> subtrees;
    int max_depth_at(int i) const {
        int res = 0;
        for (auto& s : subtrees[i]) maxi(res, s.max_depth);
        return res;
    }
};

PII farthest(const Graph& g, int src) {
    vector<int> dist(g.n, -1);
    vector<int> q = {src};
    dist[src] = 0;
    int best = src;
    for (int qi = 0; qi < SZ(q); qi++) {
        int v = q[qi];
        for (auto [u, w] : g.adj[v]) {
            if (dist[u] == -1) {
                dist[u] = dist[v] + w;
                q.PB(u);
                if (dist[u] > dist[best]) best = u;
            }
        }
    }
    return {best, dist[best]};
}

Diameter build_path_diameter(const Graph& g, int src, int dst) {
    vector<int> par(g.n, -1), par_w(g.n, 0);
    vector<bool> vis(g.n, false);
    vector<int> q = {src};
    vis[src] = true;
    for (int qi = 0; qi < SZ(q); qi++) {
        int v = q[qi];
        for (auto [u, w] : g.adj[v]) {
            if (!vis[u]) {
                vis[u] = true;
                par[u] = v;
                par_w[u] = w;
                q.PB(u);
            }
        }
    }
    Diameter res;
    for (int v = dst; v != -1; v = par[v]) {
        res.nodes.PB(v);
        if (par[v] != -1) res.edges.PB(par_w[v]);
    }
    reverse(ALL(res.nodes));
    reverse(ALL(res.edges));
    res.length = 0;
    for (int e : res.edges) res.length += e;

    vector<bool> on_path(g.n, false);
    for (int v : res.nodes) on_path[v] = true;

    vector<int> pidx(g.n, -1);
    int k = SZ(res.nodes);
    REP(i, k) pidx[res.nodes[i]] = i;

    vector<int> bfs(res.nodes.begin(), res.nodes.end());
    for (int qi = 0; qi < SZ(bfs); qi++) {
        int v = bfs[qi];
        for (auto [u, w] : g.adj[v]) {
            if (!on_path[u] && pidx[u] == -1) {
                pidx[u] = pidx[v];
                bfs.PB(u);
            }
        }
    }

    // subgraph per path node then split into branches
    res.subtrees.resize(k);
    vector<SubGraph> merged(k);
    REP(i, k) merged[i].root = res.nodes[i];
    REP(v, g.n) {
        for (auto [u, w] : g.adj[v]) {
            if (on_path[v] && on_path[u]) continue;
            int iv = pidx[v], iu = pidx[u];
            if (iv == iu && v < u) {
                merged[iv].add_edge(v, u, w);
            }
        }
    }
    REP(i, k) {
        int r = res.nodes[i];
        auto it = merged[i].adj.find(r);
        if (it == merged[i].adj.end()) continue;
        for (auto [nb, w] : it->second) {
            SubGraph branch;
            branch.root = r;
            HashSet visited;
            visited.reserve(32);
            visited.insert(r);
            visited.insert(nb);
            vector<int> bq = {nb};
            branch.add_edge(r, nb, w);
            for (int qi = 0; qi < SZ(bq); qi++) {
                int v = bq[qi];
                auto jt = merged[i].adj.find(v);
                if (jt == merged[i].adj.end()) continue;
                for (auto [x, ww] : jt->second) {
                    if (!visited.count(x)) {
                        visited.insert(x);
                        branch.add_edge(v, x, ww);
                        bq.PB(x);
                    }
                }
            }
            branch.compute_max_depth();
            res.subtrees[i].PB(branch);
        }
    }
    return res;
}

Diameter find_diameter(const Graph& g) {
    auto [a, _da] = farthest(g, 0);
    auto [b, diam_len] = farthest(g, a);
    return build_path_diameter(g, a, b);
}

int SubGraph::get_diam() const {
    if (_cached_diam >= 0) return _cached_diam;
    if (SZ(adj) < 2) {
        _cached_diam = max_depth;
        return _cached_diam;
    }
    auto [g, r] = to_graph();
    _cached_diam = (g.n < 2) ? 0 : find_diameter(g).length;
    return _cached_diam;
}

// asymmetric coordinates!!!!!!!!!!!!!!!1
// sorted by first coordinate increasing, second decreasing
vector<PII> convex_front(vector<PII> pts) {
    sort(ALL(pts), [](const PII& a, const PII& b) {
        return a.st > b.st || (a.st == b.st && a.nd > b.nd);
    });
    vector<PII> res;
    int best = -1;
    for (auto& [p1, p2] : pts) {
        if (p2 > best) {
            best = p2;
            res.PB({p1, p2});
        }
    }
    reverse(ALL(res));
    return res;
}

// sorted by first coordinate increasing, second decreasing
vector<PII> convex_from_pairs(vector<PII> pts) {
    for (auto& [a, b] : pts) if (a > b) swap(a, b);
    sort(ALL(pts), [](const PII& a, const PII& b) {
        return a.st > b.st || (a.st == b.st && a.nd > b.nd);
    });
    vector<PII> res;
    int best = -1;
    for (auto& [p1, p2] : pts) {
        if (p2 > best) {
            best = p2;
            res.PB({p1, p2});
        }
    }
    reverse(ALL(res));
    return res;
}

struct Endpoint {
    int idx; // diameter node index
    const SubGraph* sub;
    int edge_used; // how much of edge (idx, idx+1) consumed; 0 if in subtree
};

struct ReachInfo {
    VI vals;
    vector<const SubGraph*> subs; // which branch achieved max_depth (null if none)
};

// find prefix endpoint path of length x
Endpoint prefix_endpoint(int x, const MaxSeg<PII>& preach_seg, const ReachInfo& preach,
                         const VI& pdist, int K) {
    int pi = preach_seg.find_first(0, K - 1, {x, (int)-1e18});
    if (pi != -1 && pdist[pi] >= x)
        return {pi, nullptr, 0}; // diameter distance is enough
    if (pi != -1)
        return {pi, preach.subs[pi], 0}; // needs subtree
    // try pure diameter
    int i = (int)(upper_bound(pdist.begin(), pdist.begin() + K, x) - pdist.begin()) - 1;
    if (i >= 0 && i < K - 1)
        return {i, nullptr, x - pdist[i]};
    if (i == K - 1)
        return {K - 1, nullptr, 0};
    return {-1, nullptr, 0};
}

Endpoint suffix_endpoint(int x, const MaxSeg<PII>& sreach_seg, const ReachInfo& sreach,
                         const VI& sdist, int K) {
    int sj = sreach_seg.find_last(0, K - 1, {x, (int)-1e18});
    if (sj != -1 && sdist[sj] >= x)
        return {sj, nullptr, 0};
    if (sj != -1)
        return {sj, sreach.subs[sj], 0};

    int lo = 0, hi = K - 1, best = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (sdist[mid] <= x) {
            best = mid;
            hi = mid - 1;
        }
        else lo = mid + 1;
    }
    if (best > 0)
        return {best, nullptr, x - sdist[best]};
    if (best == 0)
        return {0, nullptr, 0};
    return {-1, nullptr, 0};
}

// D(0, i) + B(i)
ReachInfo diam_prefix_reach(const Diameter& d) {
    int k = SZ(d.nodes);
    VI prefix_sum(k, 0);
    FOR(i, 1, k - 1) prefix_sum[i] = prefix_sum[i - 1] + d.edges[i - 1];
    ReachInfo res;
    res.vals.resize(k);
    res.subs.resize(k, nullptr);
    REP(i, k) {
        int best_md = 0;
        for (auto& sub : d.subtrees[i]) {
            if (sub.max_depth > best_md) {
                best_md = sub.max_depth;
                res.subs[i] = &sub;
            }
        }
        res.vals[i] = prefix_sum[i] + best_md;
    }
    return res;
}

// D(j, 0) + B(j)
ReachInfo diam_suffix_reach(const Diameter& d) {
    int k = SZ(d.nodes);
    VI suffix_sum(k, 0);
    FORD(i, k - 2, 0) suffix_sum[i] = suffix_sum[i + 1] + d.edges[i];
    ReachInfo res;
    res.vals.resize(k);
    res.subs.resize(k, nullptr);
    REP(i, k) {
        int best_md = 0;
        for (auto& sub : d.subtrees[i]) {
            if (sub.max_depth > best_md) {
                best_md = sub.max_depth;
                res.subs[i] = &sub;
            }
        }
        res.vals[i] = suffix_sum[i] + best_md;
    }
    return res;
}

// convex hull of best disjoint paths - ends must touch one end of diameter
vector<PII> convex_two_paths(const Diameter& d) {
    int k = SZ(d.nodes);

    VI prefix_sum(k, 0);
    FOR(i, 1, k - 1) prefix_sum[i] = prefix_sum[i - 1] + d.edges[i - 1];

    VI suffix_sum(k, 0);
    FORD(i, k - 2, 0) suffix_sum[i] = suffix_sum[i + 1] + d.edges[i];

    VI left_max(k);
    REP(i, k) {
        int val = prefix_sum[i] + d.max_depth_at(i);
        left_max[i] = (i == 0) ? val : max(left_max[i - 1], val);
    }

    VI right_max(k + 1, 0);
    FORD(i, k - 1, 0) {
        int val = suffix_sum[i] + d.max_depth_at(i);
        right_max[i] = max(right_max[i + 1], val);
    }

    vector<PII> cands;

    // paths touch
    REP(i, k) {
        cands.PB({prefix_sum[i] + d.max_depth_at(i), suffix_sum[i]});
        cands.PB({prefix_sum[i], suffix_sum[i] + d.max_depth_at(i)});
    }

    // paths don't touch
    REP(i, k - 1) {
        cands.PB({left_max[i], right_max[i + 1]});
    }

    // full diameter + subtree diameter at any node
    REP(i, k) {
        for (auto& sub : d.subtrees[i]) {
            if (sub.adj.empty()) continue;
            int sd = sub.get_diam();
            cands.PB({d.length, sd});
        }
    }
    cands.PB({0, d.length});

    return convex_from_pairs(cands);
}

vector<PII> two_paths_raw(const Diameter& d) {
    int k = SZ(d.nodes);
    VI prefix_sum(k, 0);
    FOR(i, 1, k - 1) prefix_sum[i] = prefix_sum[i - 1] + d.edges[i - 1];

    VI suffix_sum(k, 0);
    FORD(i, k - 2, 0) suffix_sum[i] = suffix_sum[i + 1] + d.edges[i];

    VI left_max(k);
    REP(i, k) {
        int val = prefix_sum[i] + d.max_depth_at(i);
        left_max[i] = (i == 0) ? val : max(left_max[i - 1], val);
    }

    VI right_max(k + 1, 0);
    FORD(i, k - 1, 0) {
        int val = suffix_sum[i] + d.max_depth_at(i);
        right_max[i] = max(right_max[i + 1], val);
    }

    vector<PII> cands;

    REP(i, k) {
        cands.PB({prefix_sum[i] + d.max_depth_at(i), suffix_sum[i]});
        cands.PB({prefix_sum[i], suffix_sum[i] + d.max_depth_at(i)});
    }

    REP(i, k - 1) {
        cands.PB({left_max[i], right_max[i + 1]});
    }

    REP(i, k) {
        for (auto& sub : d.subtrees[i]) {
            if (sub.adj.empty()) continue;
            int sd = sub.get_diam();
            cands.PB({d.length, sd});
        }
    }
    cands.PB({0, d.length});

    return cands;
}

vector<PII> rooted_convex(const SubGraph& sg) {
    if (SZ(sg.adj) < 2) return {};
    auto [g, root] = sg.to_graph();
    if (g.n < 2) return {};
    auto d = find_diameter(g);
    int d1 = d.nodes[0], d2 = d.nodes.back();

    vector<PII> all_pts;
    for (int target : {d1, d2}) {
        auto pd = build_path_diameter(g, root, target);
        // pd.nodes[0] = root, left = rooted path, right = other path
        auto pts = two_paths_raw(pd);
        for (auto& p : pts) all_pts.PB(p);
    }
    return convex_front(all_pts);
}

// exists (p1,p2) with p1>=x and p2>=y.
// convex must be sorted by p1 increasing, p2 decreasing.
bool convex_dominates(const vector<PII>& convex, int x, int y) {
    int lo = 0, hi = SZ(convex) - 1, pos = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (convex[mid].st >= x) {
            pos = mid;
            hi = mid - 1;
        }
        else lo = mid + 1;
    }

    if (pos == -1) return false;
    return convex[pos].nd >= y;
}

struct SubtreeConvex {
    vector<PII> convex; // merged all subtrees
    int best_subtree_diam = 0;
    int second_subtree_diam = 0;
    int best_subtree_di = -1;
    int second_subtree_di = -1;

    SubtreeConvex(const Diameter& d) {
        vector<PII> all_pts;
        for (int di = 0; di < SZ(d.subtrees); di++) {
            for (auto& sub : d.subtrees[di]) {
                cerr << "  SubtreeConvex: diam_node=" << di << " adj.size=" << SZ(sub.adj) << " max_depth=" << sub.max_depth << "\n";
                if (sub.adj.empty()) continue;
                int sdl = sub.get_diam();
                cerr << "    sdl=" << sdl << "\n";
                if (sdl == 0) continue;
                if (sdl >= best_subtree_diam) {
                    second_subtree_diam = best_subtree_diam;
                    second_subtree_di = best_subtree_di;
                    best_subtree_diam = sdl;
                    best_subtree_di = di;
                } else if (sdl > second_subtree_diam) {
                    second_subtree_diam = sdl;
                    second_subtree_di = di;
                }
                auto [gg, rr] = sub.to_graph();
                auto sd = find_diameter(gg);
                auto pts = convex_two_paths(sd);
                for (auto& p : pts) all_pts.PB(p);
            }
        }
        convex = convex_from_pairs(all_pts);
    }

    bool dominates(int x, int y) const {
        return convex_dominates(convex, x, y);
    }
};

// diameter + 2 subtrees.
bool check_diam_2subtree(int a, int b, int c, const Diameter& d, const SubtreeConvex& sp) {
    int vals[] = {a, b, c};
    sort(vals, vals + 3);
    if (vals[2] > d.length) return false;
    if (sp.dominates(vals[0], vals[1])) return true;
    if (sp.best_subtree_diam >= vals[1] && sp.second_subtree_diam >= vals[0]) return true;
    return false;
}

vector<pair<int, const SubGraph*>> top3_branches(const Diameter& d) {
    vector<pair<int, const SubGraph*>> res;
    int k = SZ(d.nodes);
    REP(i, k) {
        for (auto& sub : d.subtrees[i]) {
            res.PB({sub.get_diam(), &sub});
        }
    }
    sort(ALL(res), [](auto& a, auto& b) { return a.st > b.st; });
    res.resize(min((int)3, SZ(res)));
    return res;
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); 
    int n, q;
#ifdef GENTEST
    #ifndef SEED
    #define SEED 42
    #endif
    mt19937_64 rng(SEED);
    n = 200000; q = 200000;
    Graph g(n);
    for (int i = 1; i < n; i++) {
        int p = rng() % i;
        int w = 1 + rng() % 1000000000;
        g.add_edge(p, i, w);
    }
#else
    cin >> n >> q;
    Graph g(n);
    FOR(i, 1, n - 1) {
        int u, v, w;
        cin >> u >> v >> w;
        g.add_edge(u - 1, v - 1, w);
    }
#endif
    auto diam = find_diameter(g);
    auto convex = convex_two_paths(diam);
    SubtreeConvex sp(diam);
    auto preach = diam_prefix_reach(diam);
    auto sreach = diam_suffix_reach(diam);
    const PII NEG = {(int)-1e18, -1};
    auto indexed = [&](const VI& a) {
        vector<PII> r(SZ(a));
        REP(i, SZ(a)) r[i] = {a[i], i};
        return r;
    };
    MaxSeg<PII> preach_seg(indexed(preach.vals), NEG), sreach_seg(indexed(sreach.vals), NEG);
    // prefix/suffix distance sums along diameter (without subtree max_depth)
    int K = SZ(diam.nodes);
    VI pdist(K, 0), sdist(K, 0);
    FOR(i, 1, K - 1) pdist[i] = pdist[i - 1] + diam.edges[i - 1];
    FORD(i, K - 2, 0) sdist[i] = sdist[i + 1] + diam.edges[i];
    MaxSeg<PII> pdist_seg(indexed(pdist), NEG), sdist_seg(indexed(sdist), NEG);
    // f[i] = B[i] - pdist[i], g[i] = B[i] + pdist[i] for PairSeg
    VI branch(K), fval(K), gval(K);
    REP(i, K) branch[i] = diam.max_depth_at(i);
    REP(i, K) {
        fval[i] = branch[i] - pdist[i];
        gval[i] = branch[i] + pdist[i];
    }
    PairSeg pair_seg(fval, gval);
    auto top3_branch = top3_branches(diam);
    // two best branches
    VI branch2(K, 0);
    REP(i, K) {
        int b1 = 0, b2 = 0;
        for (auto& sub : diam.subtrees[i]) {
            if (sub.max_depth >= b1) {
                b2 = b1;
                b1 = sub.max_depth;
            } else if (sub.max_depth > b2) {
                b2 = sub.max_depth;
            }
        }
        branch2[i] = b1 + b2;
    }
    MaxSeg<PII> branch2_seg(indexed(branch2), NEG);
    // convex hull for each subtree branch
    HashMap<const SubGraph*, vector<PII>> rconvex;
    REP(i, K) {
        for (auto& sub : diam.subtrees[i]) {
            if (SZ(sub.adj) >= 2)
                rconvex[&sub] = rooted_convex(sub);
        }
    }
    // subtree diameters
    HashMap<const SubGraph*, int> sub_diam;
    for (auto& [dep, sub] : top3_branch) sub_diam[sub] = dep;
    REP(i, K) {
        for (auto& sub : diam.subtrees[i]) {
            if (!sub_diam.count(&sub)) {
                sub_diam[&sub] = sub.get_diam();
            }
        }
    }
    cerr << "Diameter: length=" << diam.length << " nodes=" << diam.nodes << " edges=" << diam.edges << "\n";
    REP(i, K) {
        cerr << "  node " << i << " (id=" << diam.nodes[i] << "): pdist=" << pdist[i] << " sdist=" << sdist[i]
             << " branch=" << branch[i] << " preach=" << preach.vals[i] << " sreach=" << sreach.vals[i] << "\n";
    }
    cerr << "top3_branch:";
    for (auto& [d2, s] : top3_branch) cerr << " " << d2;
    cerr << "\n";
    cerr << "convex=" << convex << "\n";
    cerr << "sp.best_subtree_diam=" << sp.best_subtree_diam << "@di=" << sp.best_subtree_di
         << " sp.second_subtree_diam=" << sp.second_subtree_diam << "@di=" << sp.second_subtree_di << "\n";
    REP(i, q) {
        int a, b, c;
#ifdef GENTEST
        a = 1 + rng() % (int)6e14;
        b = 1 + rng() % (int)6e14;
        c = 1 + rng() % (int)6e14;
#else
        cin >> a >> b >> c;
#endif
        if (a + b + c <= diam.length) {
            debug("sum_le_diam");
            goto yes;
        }

        {
            int vals[] = {a, b, c};
            REP(lone, 3) {
                int sum = a + b + c - vals[lone];
                int lo = min(sum, vals[lone]), hi = max(sum, vals[lone]);
                if (convex_dominates(convex, lo, hi)) {
                    debug("convex_2path", lo, hi);
                    goto yes;
                }
                if (sp.best_subtree_diam >= lo && diam.length >= hi) {
                    debug("best_sub+diam", lo, hi);
                    goto yes;
                }
            }
            if (check_diam_2subtree(a, b, c, diam, sp)) {
                debug("check_diam_2sub");
                goto yes;
            }

            // perm[0] -> prefix, perm[1] -> suffix, perm[2] somewhere
            VI perm = {a, b, c};
            sort(ALL(perm));
            do {
                Endpoint pe = prefix_endpoint(perm[0], preach_seg, preach, pdist, K);
                if (pe.idx == -1) {
                    debug(perm);
                    continue;
                }
                Endpoint se = suffix_endpoint(perm[1], sreach_seg, sreach, sdist, K);
                if (se.idx == -1 || se.idx < pe.idx) {
                    debug(perm, pe.idx, se.idx, (int)(pe.sub!=nullptr), pe.edge_used, (int)(se.sub!=nullptr), se.edge_used);
                    continue;
                }
                if (se.idx == pe.idx && (pe.sub || pe.edge_used) && (se.sub || se.edge_used)) {
                    debug(perm, pe.idx, se.idx);
                    continue;
                }
                int pi = pe.idx, sj = se.idx;
                debug(perm, pi, sj, (int)(pe.sub!=nullptr), pe.edge_used, (int)(se.sub!=nullptr), se.edge_used);
                // nodes with free branches between prefix and suffix endpoints
                int gl = (pe.sub || pe.edge_used) ? pi + 1 : pi;
                int gr = (se.sub || se.edge_used) ? sj - 1 : sj;
                // perm[2] fits in best pair of branches in gap
                if (gl <= gr && pair_seg.query(gl, gr) >= perm[2]) {
                    debug("pair_seg", perm);
                    goto yes;
                }
                // perm[2] fits in two branches at a single node in gap
                if (gl <= gr && branch2_seg.query(gl, gr).st >= perm[2]) {
                    debug("branch2_seg", perm);
                    goto yes;
                }
                // prefix arm
                if (gl <= gr && preach_seg.query(gl, gr).st - pdist[pi] - pe.edge_used >= perm[2]) {
                    debug("preach_arm", perm);
                    goto yes;
                }
                // suffix arm
                if (gl <= gr && sreach_seg.query(gl, gr).st - sdist[sj] - se.edge_used >= perm[2]) {
                    debug("sreach_arm", perm);
                    goto yes;
                }
                // perm[2] fits on diameter between pi and sj
                if (pdist[sj] - pdist[pi] - pe.edge_used - se.edge_used >= perm[2]) {
                    debug("diam_between", perm);
                    goto yes;
                }
                // Check if perm[2] fits in a top branch that doesn't collide with pe/se subtrees
                for (auto& [dep, sub] : top3_branch) {
                    if (dep < perm[2]) break;
                    if (sub != pe.sub && sub != se.sub) {
                        debug("top3", perm, dep);
                        goto yes;
                    }
                }
                // extend pi to middle or flip to second branch: free pe's subtree for perm[2], relocate perm[0]
                if (pe.sub && sub_diam[pe.sub] >= perm[2]) {
                    int second = branch2[pi] - branch[pi];
                    if (pdist[pi] + second >= perm[0]) {
                        debug("move_pi_flip", perm, second);
                        goto yes;
                    }
                    if (pdist[sj] - se.edge_used >= perm[0]) {
                        debug("move_pi_diam", perm);
                        goto yes;
                    }
                    int l = preach_seg.find_first(gl, gr, {perm[0], (int)-1e18});
                    if (l != -1) {
                        debug("move_pi_reach", perm, l);
                        goto yes;
                    }
                }
                // extende sj to middle or flip to second branch: free se's subtree for perm[2], relocate perm[1]
                if (se.sub && sub_diam[se.sub] >= perm[2]) {
                    int second = branch2[sj] - branch[sj];
                    if (sdist[sj] + second >= perm[1]) {
                        debug("move_sj_flip", perm, second);
                        goto yes;
                    }
                    if (sdist[pi] - pe.edge_used >= perm[1]) {
                        debug("move_sj_diam", perm);
                        goto yes;
                    }
                    int r = sreach_seg.find_last(gl, gr, {perm[1], (int)-1e18});
                    if (r != -1) {
                        debug("move_sj_reach", perm, r);
                        goto yes;
                    }
                }
                // perm[2] cohabitates with pe's subtree
                if (pe.sub) {
                    auto it = rconvex.find(pe.sub);
                    if (it != rconvex.end()) {
                        int need_rooted = perm[0] - pdist[pi];
                        if (need_rooted >= 0 && convex_dominates(it->nd, need_rooted, perm[2])) {
                            debug("cohab_pe", perm, need_rooted);
                            goto yes;
                        }
                    }
                }
                // perm[2] cohabitates with se's subtree
                if (se.sub) {
                    auto it = rconvex.find(se.sub);
                    if (it != rconvex.end()) {
                        int need_rooted = perm[1] - sdist[sj];
                        if (need_rooted >= 0 && convex_dominates(it->nd, need_rooted, perm[2])) {
                            debug("cohab_se", perm, need_rooted);
                            goto yes;
                        }
                    }
                }
            } while (next_permutation(ALL(perm)));
        }
        cout << "NIE\n";
        continue;
        yes:
        cout << "TAK\n";
    }
    return 0;
}