题目描述

独立出题者国家（ICPC）政$$府终于攒够了建设高速铁路系统的资金。新铁路系统包含 $V$ 个车站和 $E$ 条双向直达铁路线，每条线路连接两个车站。ICPC 铁路基础设施规划负责人 Skib E. Dee 深知树形拓扑交通网络的弊端：单条铁路线损坏会导致网络分裂，造成数日交通中断。因此，Dee 决定将 ICPC 铁路网络设计为强健连通：任意两个车站 $s_1$ 和 $s_2$ 之间必须存在至少两条路径，这两条路径不共享任何直达铁路线，且除 $s_1$ 和 $s_2$ 外不共享任何车站。

当然，ICPC 无法承担过多冗余铁路线的建设成本。为平衡效率与鲁棒性，Dee 还将网络设计为区域连通。一个环是指从某车站出发回到自身且不重复经过任何车站（起始车站仅在开头和结尾各出现一次）的非空路径。要实现区域连通，必须存在由 $E-V+1$ 个区域环组成的集合 $\mathcal{F}$，满足以下三个性质：

• 交通网络中每条直达铁路线至少属于一个区域环；
• 若两个区域环共享任何直达铁路线，则它们共享的所有铁路线和车站必须构成一条连通路径；
• 对于 $\mathcal{F}$ 的任意子集 $f$，其中共享铁路线的区域环对数不超过 $|f|-1$。

为宣传新高铁，Dee 需要制作一段火车沿铁路环线行驶的延时视频。每条直达铁路线都有一个（可能为负的）风景值，表示沿线车窗外的景色优美程度。Dee 希望选择风景值总和最大的环线作为拍摄路线（该环线不必是区域环）。为确保环线不单调，它必须包含至少两条铁路线，且不重复经过任何车站（起始车站仅在开头和结尾各出现一次）。

输入格式

第一行输入两个整数 $V$（$2 \leq V \leq 2 \cdot 10^5$）和 $E$（$V \leq E \leq 4 \cdot 10^5$），分别表示车站数量和直达铁路线数量。

接下来 $E$ 行描述直达铁路线，每行包含三个整数 $a$、$b$ 和 $s$（$1 \leq a,b \leq V$；$-10^9 \leq s \leq 10^9$），表示车站 $a$ 与 $b$ 之间存在一条风景值为 $s$ 的直达铁路线。没有铁路线连接同一车站，但同一对车站间可能存在多条铁路线。保证输入图既是强健连通的，也是区域连通的。

输出格式

输出铁路网络中风景值总和最大的环线的风景值总和。

输入输出样例 #1

输入 #1

6 9
1 2 9
2 3 9
3 4 9
3 4 -9
4 1 9
1 5 1
5 6 1
6 2 1
3 4 8

输出 #1

36

输入输出样例 #2

输入 #2

5 7
1 2 1
2 3 -2
3 4 3
4 5 6
5 1 4
5 3 2
2 5 9

输出 #2

16

说明/提示

对于样例输入 2 的铁路网络，集合 $\mathcal{F}$ 的区域环可选为 $1 \rightarrow 2 \rightarrow 5 \rightarrow 1$、$2 \rightarrow 5 \rightarrow 3 \rightarrow 2$ 和 $3 \rightarrow 4 \rightarrow 5 \rightarrow 3$（左图）。风景值总和最大的环线（右图蓝色路径）的风景值总和为 $9+6+3-2=16$。