题目描述

Matei Nakayama Mihai 得到了一棵仙人掌。

一个仙人掌图是一个连通无向图，其中每个点至多属于一个简单环。现在给定一个有 $N$ 个点、$M$ 条边的带权仙人掌图。图中没有自环，也没有重边。

Mihai 想从这个仙人掌图中删除若干条边，使剩下的图成为一棵树，并且这棵树尽可能“轻”。

一棵树中两点之间的距离定义为它们之间唯一简单路径上的边权和。树的权重定义为所有无序点对 $(u,v)$，$u\ne v$，之间距离之和。

请你求出从给定仙人掌图中删除若干边后，能够得到的树的最小权重。

输入格式

第一行包含两个整数 $N,M$，分别表示点数和边数。

接下来 $M$ 行，每行包含三个整数 $x,y,z$，表示点 $x$ 与点 $y$ 之间有一条长度为 $z$ 的无向边。

输出格式

输出一个整数，表示能够得到的树的最小权重。

数据范围

• $1\le N\le 100000$；
• $N-1\le M\le 200000$；
• $0\le z\le 10^9$；
• 保证答案不超过 $10^{18}$。

子任务

样例

样例 1

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

80

一种最优做法是删除边 $(1,2)$。

样例 2

12 14
1 2 7
2 3 3
1 3 7
3 4 2
4 5 5
5 6 10
6 4 3
4 7 4
7 8 2
8 9 5
9 10 8
10 11 1
11 7 9
10 12 3

787

一种最优做法是删除边 $(1,2)$、$(5,6)$、$(9,10)$。