Road Reparation

题目描述

有 n 个城市和它们之间的 m 条公路。不幸的是，这些公路状况太差，无法使用。你的任务是修复其中一些公路，使得任意两座城市之间都有一条通路可达。\n对于每条公路，你知道它的修复费用，你应该找到一个使总费用尽可能小的方案。

输入格式

第一行输入包含两个整数 n 和 m：城市数和公路数。城市编号为 1,2,$\dots$,n。\n随后有 m 行描述这些公路。每行有三个整数 a, b 和 c：城市 a 和 b 之间有一条公路，其修复费用为 c。所有公路都是双向的。\n每条公路连接两个不同的城市，并且任意两座城市之间最多有一条公路。

输出格式

输出一个整数：最小的总修复费用。如果不存在可行方案，则输出 "IMPOSSIBLE"。

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

14

提示

$1 \le n \le 10^5$ $1 \le m \le 2 \cdot 10^5$ $1 \le a,b \le n$ $1 \le c \le 10^9$

标签: CSES1675|图论

来源

CSES1675|图论