1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define int long long
#define ld long double
#define pb push_back

using namespace std;
#define rg ranges

int n, q;
vector<vector<pair<int, int>>> g;
vector<array<int, 2>> diam;
vector<int> lowest;
int lg;
vector<vector<int>> st;

pair<int, int> dfsFrth(int v, int p) {
    pair<int, int> ret = {0, v};
    repIn2(u, c, g[v]) if(u != p) {
        auto x = dfsFrth(u, v);
        x.first += c;
        ret = max(ret, x);
    }
    return ret;
}

int dst;
bool dfsDiam(int v, int p, int U) {
    if(v == U) {
        diam.pb({U, dst});
        return 1;
    }
    repIn2(u, c, g[v]) if(u != p) {
        dst += c;
        auto x = dfsDiam(u, v, U);
        dst -= c;
        if(x) {
            diam.pb({v, dst});
            return 1;
        }
    }
    return 0;
}

void dfsLowest(int v, int p1, int p2) {
    repIn2(u, c, g[v]) if(u != p1 && u != p2) dfsLowest(u, v, v), lowest[v] = max(lowest[v], lowest[u] + c);
}

int stQ(int l, int r) {
    int k = 31 - __builtin_clz((int32_t)(r - l + 1));
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> q;
    g.resize(n + 1);
    lowest.resize(n + 1);
    rep(i, 1, n) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].pb({b, c});
        g[b].pb({a, c});
    }
    auto [_1, d1] = dfsFrth(1, 0);
    auto [_2, d2] = dfsFrth(d1, 0);
    dfsDiam(d1, 0, d2);
    rg::reverse(diam);
    int d = (int) diam.size();
    rep(i, 0, d) dfsLowest(diam[i][0], (i ? diam[i - 1][0] : 0), (i + 1 < d ? diam[i + 1][0] : 0));
    //rep(i, 0, d) diam[i][2] = max((i ? diam[i - 1][2] : -1), diam[i][1] + lowest[diam[i][0]]);
    lg = 32 - __builtin_clz((int32_t)d);
    st.resize(d, vector<int>(lg));
    rep(i, 0, d) st[i][0] = diam[i][1] + lowest[diam[i][0]];
    rep(k, 1, lg) rep(i, 0, d) st[i][k] = max(st[i][k - 1], st[min(d - 1, (int)i + (1 << (k - 1)))][k - 1]);
    while(q--) {
        array<int, 3> arr;
        rep(i, 0, 3) cin >> arr[i];
        bool gg = 0;
        do { rep(msk, 0, 1 << 2) {
            int lt = 0;
            int subt = 0;
            gg = 1;
            rep(i, 0, 3) {
                int l = lt, m, r = d;
                while(r - l > 1) {
                    m = (l + r) / 2;
                    if( ((~(msk >> i) & 1) ? diam[m][1] : stQ(lt, m))  - subt >= arr[i]) r = m;
                    else l = m;
                }
                if(r == d) { gg = 0; break; }
                lt = r - 1;
                if(~(msk >> i) & 1) subt = diam[r][1] - max(lowest[diam[r][0]], diam[r][1] - subt - arr[i]);
                else subt = diam[r][1];
            }
            if(gg) break;
        }} while(!gg && rg::next_permutation(arr).found);
        cout << (gg ? "TAK" : "NIE") << '\n';
    }
}