CF1223E Paint the Tree

给定一个有 $N$ 个节点的树，每个节点要染上 $K$ 种颜色，有无数多种颜色，每种颜色最多用两次。当一条边的两个节点附上的颜色中有至少一种相同颜色时，这条边的贡献就是它的权值，否则贡献为 $0$。 求这颗树所有边最大的贡献之和。

共 $T$ 组数据，每组数据第一行 2 个数字，分别为 $N$ 和 $K$。 之后的 $N-1$ 行，每行3个数字 $u,v,w$，表示节点 $u$ 和 $v$ 之间有一个权值为 $w$ 的边（$u \neq v$）。

共 $T$ 行，每行一个整数，表示这棵树所有边最大的贡献之和。

$1\le T\le 5\cdot 10^5,1\le N,K\le 5\cdot 10^5$，保证所有 $N$ 之和小于等于 $5\cdot 10^5$。