山路连线计划

题目描述

有 n 个村庄和 m 条可修建的山路，每条山路连接两个村庄并有修建费用。请用最少费用让所有村庄互相可达；如果无法做到，输出 -1。

输入格式

第一行两个整数 n 和 m。
接下来 m 行，每行三个整数 a、b、w，表示修建连接 a 与 b 的山路需要 w 的费用。

输出格式

输出最小总费用；如果无法连通所有村庄，输出 -1。

数据范围

1 <= n <= 200000
0 <= m <= 300000
1 <= w <= 10^9

第一行两个整数 n 和 m。
接下来 m 行，每行三个整数 a、b、w，表示修建连接 a 与 b 的山路需要 w 的费用。

输出最小总费用；如果无法连通所有村庄，输出 -1。

1 <= n <= 200000
0 <= m <= 300000
1 <= w <= 10^9