#P16039. [Oni2023国家队选拔赛]Cactus

[Oni2023国家队选拔赛]Cactus

题目描述

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

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

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

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

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

输入格式

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

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

输出格式

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

数据范围

  • 1≤N≤1000001\le N\le 100000;
  • N−1≤M≤200000N-1\le M\le 200000;
  • 0≤z≤1090\le z\le 10^9;
  • 保证答案不超过 101810^{18}。

子任务

子任务 分值 限制
1 4 图是一条链,即没有环且每个点度数不超过 22
2 6 图是一棵树,即没有环
3 12 1≤N≤151\le N\le 15
4 25 1≤N≤10001\le N\le 1000
5 38 图本身是一个环,即每个点度数为 22
6 15 无额外限制

样例

样例 1

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

一种最优做法是删除边 (1,2)(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)(1,2)、(5,6)(5,6)、(9,10)(9,10)。