T151593 树上的树

**本题自动开启 O2 优化。**

给你一个 $n$ 个节点的树，你需要在树上的每一个节点上都种上一棵树。 为了使种的树看起来更美观，我们准备了 $m$ 种树。 对于每种树，我们都有一条特定的**简单路径**（由一组点对 $(u,v)$ 来表示，包括端点），如果一种方案在路径上的所有点都种上了这种树，那么这个方案会累加上 $w$ 的美观度。 因为出题人很懒，你只需要给出这个最大化的美观度的和，不需要输出方案。

第一行两个正整数 $n,m$。 第二行到第 $n$ 行，每行两个正整数 $x,y$ 表示树上的一条边。 第 $n+1$ 行到第 $n+m$ 行，每行三个正整数 $u,v,w$ 即代表在树上的一条由 $u$ 到 $v$ 唯一路径都种上这种树后，获得的美观度为 $w$。

一行一个数 $ans$ 表示最大化的美观度。

**注意：本题的读入量较大，请使用较快的读入方式。** Subtask 1（5 分）: $n,m\le 18$。 Subtask 2（7 分）: 不存在节点使得有两个以上其他节点和他相连。 Subtask 3（13 分）: $n,m\le 2\times 10^3$ ，且所有的 $w=1$。 Subtask 4（38 分）: $n,m\le 2\times 10^5$。 Subtask 5（37 分）: 无特殊限制。 对于全部的数据，保证： - $2\le n,m\le 10^6$ - $1\le x,y,u,v\le n$ - $w\le 2\times 10^9$