#216037. [PA 2026] 我们今天调试雪人吗？/ Zbugujemy dziś bałwana?

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

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

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

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

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

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

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

输入的第一行包含两个整数 和 （），分别表示 Bajtogóra 的路口数量以及方案数量。

接下来 行，每行包含三个整数 和 （），描述一条连接路口 和 的街道，该街道上有 单位的雪。

接下来 行，每行描述一个雪人方案，包含三个整数 （），描述第 个方案中各雪球的大小。

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

样例输入 1

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

样例输出 1

NIE
TAK
TAK
NIE
TAK
TAK
TAK
TAK
TAK
NIE
NIE

样例解释

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

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

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

  • （最后一条街道部分使用），收集 单位的雪。
  • （最后一条街道部分使用），收集 单位的雪。
  • 街道 的剩余部分还剩 单位的雪，足以建造第三个雪球。

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

  • ，收集 单位的雪。
  • ，收集 单位的雪。
  • ，收集 单位的雪。

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

• 建造雪人 无法使用如下路径：

  • ，
  • ，
  • 。

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

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

  • ，收集 单位的雪。
  • ，收集 单位的雪。
  • ，收集 单位的雪。

子任务

各测试组按附加约束条件 的值排序。在第 1 组中， 的总和不超过 。在第 1、3 和 5 组中，有附加条件 。