#M. 最小生成树

传统题

1500ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

提示：Prim 算法请开 O2 优化。

给出一个无向图，求出最小生成树

第一行包含两个整数 $N,M$ ，表示该图共有 $N$ 个结点和 $M$ 条无向边。

接下来 $M$ 行每行包含三个整数 $X_i,Y_i,Z_i$ ，表示有一条长度为 $Z_i$ 的无向边连接结点 $X_i,Y_i$ 。

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和

$1\le N\le 5\times 10^5$

$1\le M\le 5\times 10^5$

$1 \le X_i,Y_i \le N$

$1\le Z_i \le 10^4$

$X_i ≠ Y_i$