P6618 岛屿 Island

> 从前有些岛，岛旁有些桥；桥连着岛，岛连着桥。 > > 有一天，桥倒了，岛翘了；从此桥没了岛，岛也没了桥。

茫茫大海中央，有一个庞大的群岛体系，坐落着 $n$ 座岛屿。为了方便记录，我们把它们编号为岛屿 $1$ 到 $n$，其中，岛屿 $1$ 是唯一一个有人居住的岛。 这些群岛间，有 $m$ 架摇摇欲坠的小桥。第 $i$ 架桥连接着 $u_i, v_i$ 两座 **不同** 的岛，**没有两座岛之间架有两架桥**。 脆弱的小桥已经荒废了，每架桥都只能容一个人走一遍就会倒塌。 一天，你心血来潮，前来这个庞大的群岛探险。作为探险家的你，知道一条安全的岛屿探险路径 **可以多次踏足同一个岛屿**，但 **绝不能走倒塌的桥**； 一条有趣的岛屿探险回路是一条 **以同一个岛屿为起点和终点** 的安全岛屿探险路径，并且它至少踏足两个不同的岛屿。 但特别的，**有趣的岛屿探险回路除了起点能经过两次以外，其它的岛屿都只能经过一次**（显然，你当然不觉得重复探访你已经踏足过的岛屿很有趣）。 为了保证你的安全，你做足了功课，拿到了群岛的地图。仔细研究这个古老的地图，你发现每两个岛之间都有至少一条路可以抵达，并且第 $i$ 架桥上竟然藏着价值为 $w_i$ 的宝藏！ 然而，你又发现群岛间的桥是非常稀少的，这些桥总是满足一个规律：**以同一个岛屿为起点的不同的有趣探险回路一定不会经过相同的一架桥**。 你将可以空降到任意一个岛屿开始你的探险，途中你可以收集宝藏，但最终你 **必须回到岛屿** $1$，才能安全地返回。 现在，你想知道在 **确保自己安全** 的情况下最大的能收集到的宝藏的价值和。

第一行两个正整数 $n, m$，表示小岛的数量和连接小岛的桥梁的总数量； 接下来的 $m$ 行，每行共三个正整数，其中第 $i$ 行为 $u_i, v_i, w_i$ ，含义如题。

一行共一个整数，表示在 **确保自己安全** 的情况下最大的能收集到的宝藏的价值和。

本题采用 **捆绑测试**，开启 **O2优化**。 $\text{Subtask 1 (3 pts)}:$ 保证不存在有趣的探险回路； $\text{Subtask 2 (7 pts)}:$ 保证 $1 \le n \le 10$； $\text{Subtask 3 (10 pts)}:$ 保证没有两个有趣的探险回路经过同一个岛屿； $\text{Subtask 4 (10 pts)}:$ 保证 $w_i = 1$； $\text{Subtask 5 (20 pts)}:$ 保证 $1 \le n \le 2000$； $\text{Subtask 6 (20 pts)}:$ 保证 $1 \le n \le 10^5$； $\text{Subtask 7 (30 pts)}:$ 没有特殊限制。 对于所有数据，满足 $1 \le n \le 3\times10^5$，$1 \le m \le10^6$，$1 \le w_i \le 10^9$。 --- #### 样例 #1 解释  > 上为群岛的地图，圆圈代表岛屿，圆圈间的线代表桥， > > 圆圈中的数字是岛屿的编号，线旁的数字是桥上宝藏的价值。  从 $7$ 号岛屿出发，沿着上图的方向和顺序走，收集到的宝藏价值和为 $15$，即为答案。