P12626 [ICPC 2025 NAC] Most Scenic Cycle

独立出题者国家（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$ 的直达铁路线。没有铁路线连接同一车站，但**同一对车站间可能存在多条铁路线**。保证输入图既是**强健连通**的，也是**区域连通**的。

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

对于样例输入 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$。  翻译由 DeepSeek V3 完成