给定一个简单的连通图，其中每条边都被赋予一个非负权重。回想一下，图的最小生成树是图的一个连通、无环的边子集，其总权重最小。请找到这样一条边：删除该边后，剩余图的最小生成树权重最大。题目保证删除任意一条边后，输入图仍然保持连通。

输入格式

第一行包含两个整数 $n$ ($3 \le n \le 10^5$) 和 $m$ ($3 \le m \le 10^6$)，其中 $n$ 是顶点数，$m$ 是输入图中的边数。顶点编号从 $1$ 到 $n$。

接下来的 $m$ 行，每行包含三个整数 $a, b$ ($1 \le a < b \le n$) 和 $w$ ($1 \le w \le 10^6$)。这表示顶点 $a$ 和 $b$ 之间存在一条权重为 $w$ 的边。

输出格式

输出一个整数，表示删除“正确”的边后，输入图的最小生成树权重。

样例

输入 1

3 3
1 2 1
2 3 2
1 3 2

输出 1

4

输入 2

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

输出 2

10

输入 3

5 7
2 5 8
1 3 19
4 5 9
1 5 15
1 2 14
3 4 16
2 4 15

输出 3

54