在图论的数学学科中，简单无向加权图 $G$ 的线图 $L(G)$ 是另一个简单无向加权图，它表示了 $G$ 中每两条边之间的邻接关系。

确切地说，对于一个没有自环或重边的无向加权图 $G$，其线图 $L(G)$ 是一个无向加权图，满足：

• $L(G)$ 的每个顶点代表 $G$ 的一条边；
• $L(G)$ 的两个顶点相邻，当且仅当它们在 $G$ 中对应的边共享一个公共端点，且这两个顶点之间的边权为它们在 $G$ 中对应边权之和。

简单无向加权图中的最大权匹配定义为一组边，使得其中任意两条边都不共享公共顶点，且该集合中所有边的权重之和最大。

给定一个简单无向加权连通图 $G$，你的任务是求出 $L(G)$ 的最大权匹配中所有边的权重之和。

输入格式

第一行包含两个整数 $n$ ($3 \le n \le 10^5$) 和 $m$ ($n-1 \le m \le \min(\frac{n(n-1)}{2}, 2 \times 10^5)$)，分别表示给定图 $G$ 的顶点数和边数。

接下来 $m$ 行，第 $i$ 行包含三个整数 $u, v$ ($1 \le u, v \le n$) 和 $w$ ($1 \le w \le 10^9$)，表示图 $G$ 中的第 $i$ 条边连接顶点 $u$ 和 $v$，权重为 $w$。

保证图 $G$ 是连通的，且不包含自环或重边。

输出格式

输出一行，包含一个整数，表示 $L(G)$ 的最大权匹配中所有边的权重之和。

样例

输入格式 1

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

输出格式 1

21

输入格式 2

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

输出格式 2

12

输入格式 3

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

输出格式 3

14