P15895 [TOPC 2025] One-Way Abyss

米蒂是一位勇敢的冒险家，正在探索一个名为“深渊”的神秘地下洞穴系统。深渊由 $n$ 条垂直的竖井和 $m$ 条水平的隧道组成。每条隧道恰好连接同一深度上的两条竖井。所有 $m$ 条隧道的深度各不相同，而且令人惊奇的是，每条隧道的正中央都有一份宝藏！ 米蒂可以选择任意一条竖井作为起点。他从所选竖井的顶部开始向下移动，并遵循以下规则： - 他只能向下移动，不允许向上移动。 - 每当遇到一条水平隧道时，他 **必须** 立即进入这条隧道，并到达与之相连的另一条竖井。 - 一旦进入一条水平隧道，就无法原路返回。 这些隧道中的宝藏具有不同的价值。米蒂希望尽可能多地收集宝藏。请帮助他计算，从某条竖井出发时，他最多能收集到的宝藏总价值。

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$，接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$，分别表示竖井的数量和水平隧道的数量。 接下来的 $m$ 行，每行包含三个整数 $x$、$y$ 和 $v$，表示一条位于某个深度的水平隧道，连接编号为 $x$ 和 $y$ 的两条竖井，且隧道内包含一份价值为 $v$ 的宝藏。 水平隧道按照从上到下的顺序给出，这意味着不会有两条水平隧道处于同一深度。

对于每个测试用例，输出一个整数，表示米蒂能够收集到的最大宝藏总价值。

- $1 \le t \le 20$ - $1 \le n \le 2 \times 10^5$ - $0 \le m \le 2 \times 10^5$ - $1 \le x < y \le n$ - $0 \le v \le 10^9$ - 保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。 - 保证所有测试用例的 $m$ 之和不超过 $2 \times 10^5$。 翻译由 DeepSeek V3.2 完成