题目背景

警告：滥用本题评测，一次即可封号。

---

「zbugujemy」（英语「bug」）：制造故障/调试。

题目描述

今晚，Bajtogóra 降下了今年的第一场雪。作为这座城市的市长，你决定借助除雪的机会，堆一个巨大的雪人来庆祝这一时刻。城市中共有 $n$ 个路口，编号从 1 到 $n$，由 $n-1$ 条双向街道相连（死胡同的端点处也有路口）。从任意一个路口出发，均可沿街道到达任意其他路口。对于每条街道，已知它连接的两个路口以及它的长度。雪均匀地降落在各处，即长度为 $w$ 的道路上积了 $w$ 单位的雪。

雪人将由三个雪球组成，每个雪球通过沿某条简单路径滚雪而成。路径可以从某个路口或某条街道上的任意一点出发，经过若干不同的街道和路口，最终在某条街道上的任意一点或某个路口处结束。滚好的雪球将由直升机运至雪人的建造地点。

任意两条路径不能经过同一个点，否则会导致雪球沾上泥土。更确切地说，Bajtogóra 地图上的任意一点（尤其是路口）都不能成为两条不同路径的内部点。我们假设在开始或结束滚雪球的那个点处不收集雪，因此同一个点可以是多条路径的起点或终点（同时，路径也可以在另一条路径的内部点处开始或结束）。

你尚未决定雪人各部分的大小，因此还不清楚每个雪球需要多少雪。你正在考虑 $q$ 个潜在方案；每个方案由三个整数 $a_i \le b_i \le c_i$ 描述，表示各雪球的大小（从上到下）。

对于每个方案，判断能否按上述方式建造雪人。

输入格式

输入的第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 200\,000,\ 1 \le q \le 200\,000$），分别表示 Bajtogóra 的路口数量以及方案数量。

接下来 $n-1$ 行，每行包含三个整数 $u_i, v_i$ 和 $w_i$（$1 \le u_i, v_i \le n;\ 1 \le w_i \le 10^9$），描述一条连接路口 $u_i$ 和 $v_i$ 的街道，该街道上有 $w_i$ 单位的雪。

接下来 $q$ 行，每行描述一个雪人方案，包含三个整数 $a_i, b_i, c_i$（$1 \le a_i \le b_i \le c_i \le 10^{15}$），描述第 $i$ 个方案中各雪球的大小。

输出格式

输出共 $q$ 行；若第 $i$ 个方案可以建造雪人，则第 $i$ 行输出 TAK，否则输出 NIE。

9 11
1 2 25
2 3 2
2 4 5
1 5 5
1 6 6
1 7 1
7 8 2
7 9 2
57 57 57
12 12 12
6 8 30
1 8 31
7 7 25
10 15 15
5 11 27
5 7 31
4 5 36
12 12 13
7 7 26

NIE
TAK
TAK
NIE
TAK
TAK
TAK
TAK
TAK
NIE
NIE

提示

样例解释

::::aligned{center} ::::

• 第一个方案（雪球大小为 $57, 57, 57$）无法实现。城市中的雪量不足以建造如此巨大的雪人。

• 建造雪人 $12, 12, 12$ 可以使用如下路径：

  • $6-1-2$（最后一条街道部分使用），收集 $6 + 6 = 12$ 单位的雪。
  • $4-2-1$（最后一条街道部分使用），收集 $5 + 7 = 12$ 单位的雪。
  • 街道 $1-2$ 的剩余部分还剩 $25 - 6 - 7 = 12$ 单位的雪，足以建造第三个雪球。

• 建造雪人 $6, 8, 30$ 可以使用如下路径：

  • $1-6$，收集 $6$ 单位的雪。
  • $5-1-7-8$，收集 $5 + 1 + 2 = 8$ 单位的雪。
  • $1-2-4$，收集 $25 + 5 = 30$ 单位的雪。

  注意路口 $1$ 仅位于一条路径的内部，因此不会有雪球沾上泥土。

• 建造雪人 $1, 8, 31$ 无法使用如下路径：

  • $2-3$，
  • $5-1-6$，
  • $7-1-2-4$。

  尽管雪量足够，但有两条路径使用了路口 $1$ 处的雪，这会导致其中一个雪球沾上泥土。

• 建造雪人 $7, 7, 25$ 可以使用如下路径：

  • $3-2-4$，收集 $2 + 5 = 7$ 单位的雪。
  • $6-1-7$，收集 $6 + 1 = 7$ 单位的雪。
  • $1-2$，收集 $25$ 单位的雪。

子任务

各测试组按附加约束条件 $n$ 的值排序。在第 1 组中，$w_i$ 的总和不超过 $60$。在第 1、3 和 5 组中，有附加条件 $q \le 200$。