题目描述

有 $n$ 个地点和 $m$ 条双向道路。地点从 $1$ 到 $n$ 编号，道路从 $1$ 到 $m$ 编号。第 $i$ 条道路连接地点 $u_i, v_i$，长度为 $w_i$。同一对地点之间可能有多条道路，它们视作不同的道路。

你需要选择一条路线，从某个地点出发，恰好经过每条道路一次，最后回到出发地点。道路网络连通，且每个地点连接的道路条数均为偶数。

设一条路线按经过顺序的道路编号为 $e_1,e_2,\ldots,e_m$，并令 $e_{m+1}=e_1$。定义这条路线的代价为

$$ \max_{1\le j\le m}\left(w_{e_j}+w_{e_{j+1}}\right). $$

也就是说，最后经过的道路与最先经过的道路也视为相邻。求路线代价的最小可能值。

输入格式

第一行两个正整数 $n, m$，分别表示地点数和道路数。

接下来 $m$ 行，第 $i$ 行三个正整数 $u_i, v_i, w_i$，用空格分隔，表示第 $i$ 条道路连接地点 $u_i, v_i$，长度为 $w_i$。

输出格式

输出一行一个整数，表示路线代价的最小可能值。

输入/输出样例 #1

5 6
1 2 1
2 3 1
3 1 4
1 4 2
4 5 1
5 1 3

6

输入/输出样例 #2

3 3
1 2 9
2 3 1
3 1 9

18

数据范围与提示

对于所有数据，$2\le n\le m\le 3\times 10^5$，$1\le u_i,v_i\le n$，$u_i\ne v_i$，$1\le w_i\le 10^9$。

保证道路网络连通，且每个地点连接的道路条数均为偶数。

本题采用子任务捆绑计分。只有通过一个子任务的全部测试点，才能获得该子任务的分数。总分为 $100$ 分。

$$ \begin{array}{|c|c|c|c|c|} \hline \text{子任务编号} & \text{分值} & n\leq & m\leq & \text{特殊限制} \\ \hline \text{1} & 10 & 10 & 10 & \text{-} \\ \hline \text{2} & 15 & 18 & 18 & \text{-} \\ \hline \text{3} & 10 & 3\times 10^5 & 3\times 10^5 & \text{所有边权相等} \\ \hline \text{4} & 10 & 3\times 10^5 & 3\times 10^5 & \text{每个点的度数均为 }2 \\ \hline \text{5} & 20 & 3\times 10^5 & 3\times 10^5 & \text{每个点的度数不超过 }4 \\ \hline \text{6} & 35 & 3\times 10^5 & 3\times 10^5 & \text{-} \\ \hline \end{array} $$