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
#include <bits/stdc++.h>
using namespace std;

void chmax(int64_t& x, int64_t y) {
  if (x < y) x = y;
}

array<int64_t, 8> e() {
  array<int64_t, 8> res;
  fill(res.begin(), res.end(), -1);
  return res;
}

int main () {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector<vector<pair<int, int>>> G(n);
  for (int i = 0; i < n-1; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    G[u].emplace_back(v, w);
    G[v].emplace_back(u, w);
  }

  vector<array<int64_t, 8>> dp(n);

  while (q--) {
    int64_t a, b, c;
    cin >> a >> b >> c;
    // cout << a << ' ' << b << ' ' << c << '\n';
    array<int64_t, 8> subset_sum;
    for (int i = 0; i < 8; i++) {
      subset_sum[i] = 0;
      if (i&1) subset_sum[i] += a;
      if (i&2) subset_sum[i] += b;
      if (i&4) subset_sum[i] += c;
    }
    for (int i = 0; i < n; i++) fill(dp[i].begin(), dp[i].end(), -1);
    auto dfs = [&] (this auto self, int v, int p) -> void {
      dp[v] = e();
      array<int64_t, 8> s1 = e();
      array<int64_t, 8> s2 = e();
      s1[0] = s2[0] = 0;
      for (auto& [u, w]: G[v]) {
        if (u == p) continue;
        self(u, v);
        array<int64_t, 8> ns1 = s1, ns2 = s2;
        for (int su = 0; su < 8; su++) {
          if (dp[u][su] < 0) continue;
          for (int sv = 0; sv < 8; sv++) {
            if (s1[sv] >= 0) {
              chmax(ns2[su|sv], dp[u][su]+w+s1[sv]);
              chmax(ns1[su|sv], max(dp[u][su]+w, s1[sv]));
              for (int m = 0; m < 8; m++) {
                if (dp[u][su]+w >= subset_sum[m]) {
                  chmax(ns1[su|sv|m], s1[sv]);
                  chmax(ns2[su|sv|m], s2[sv]);
                }
                if (s1[sv] >= subset_sum[m]) chmax(ns1[su|sv|m], dp[u][su]+w);
              }
            }
            if (s2[sv] >= 0) {
              chmax(ns2[su|sv], s2[sv]);
            }
          }
        }

        swap(s1, ns1);
        swap(s2, ns2);
        // if (v == 5) {
        //   cout << "*v = " << v+1 << '\n';
        //   cout << "u = " << u+1 << '\n';
        //   for (auto& x: dp[v]) cout << x << ' ';
        //   cout << '\n';
        //   for (auto& x: s1) cout << x << ' ';
        //   cout << '\n';
        //   for (auto& x: s2) cout << x << ' ';
        //   cout << '\n';
        //   cout << '\n';
        // }
      }
      for (int i = 0; i < 8; i++) {
        // if (v == 0) cout << i << ' ' << dp[v][i] << ' ' << s1[i] << ' ' << s2[i] << '\n';
        chmax(dp[v][i], s1[i]);
        chmax(s2[i], s1[i]);
        for (int m = 0; m < 8; m++) {
          if (s2[i] >= subset_sum[m]) chmax(dp[v][i|m], 0);
        }
      }

      // cout << "v = " << v+1 << '\n';
      // for (auto& x: s1) cout << x << ' ';
      // cout << '\n';
      // for (auto& x: s2) cout << x << ' ';
      // cout << '\n';
      // for (auto& x: dp[v]) cout << x << ' ';
      // cout << '\n';
      // cout << '\n';
    };
    dfs(0, -1);
    cout << (dp[0][7] < 0 ? "NIE" : "TAK") << '\n';
  }
}