不妨看看这组数据

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

提供一个简单粗暴的解决方式：枚举每个权值建出邻接矩阵后，先 dfs 一遍，在连通块间连一条边（即手动连成树，显然不会影响答案）