题目描述

ICPC 王国是一个拥有 $N$ 个城市的大王国，城市编号从 $1$ 到 $N$。ICPC 王国的魅力在于其境内美丽的风景。为了推广这些风景，ICPC 王国的国王决定在风景附近修建 $M$ 条收费公路，编号从 $1$ 到 $M$，供游客欣赏。要使用连接城市 $U_i$ 和 $V_i$ 的双向收费公路 $i$，必须支付 $W_i$。通过这些收费公路，可以从一个城市前往任何其他城市。

尽管这些收费公路已经建成并可以使用，但它们仍然没有吸引到游客。国王决定推出一个促销活动：游客可以预先支付他们想要使用的收费公路的费用，并且只要不离开 ICPC 王国，就可以多次使用这些公路。

这个想法终于吸引了游客，但出现了一种奇怪的行为。所有游客只支付那些能让他们从一个城市前往任何其他城市（无论距离）且总支付费用最小的收费公路集合。有趣的是，在当前收费定价下，这样的收费公路集合是唯一的。这种奇怪的行为并没有让游客充分领略王国的风景。

为了推广更多风景，国王决定提高一些收费公路的价格。如果在提价前，游客的奇怪行为使用了收费公路 $i$，那么在提价后，国王必须确保收费公路 $i$ 不被游客的奇怪行为使用。为了稳定性，国王还希望所有收费公路的总提价幅度尽可能小。

国王请你计算满足国王计划所需的最小总提价幅度，或者报告这是不可能的。

输入格式

输入以两个整数 $N$ $M$（$2 \leq N \leq 100\,000$；$N-1 \leq M \leq 200\,000$）开始，分别表示城市数量和收费公路数量。接下来的 $M$ 行，每行包含 $3$ 个整数 $U_i$ $V_i$ $W_i$（$1 \leq U_i < V_i \leq N$；$1 \leq W_i \leq 10^9$），表示连接城市 $U_i$ 和 $V_i$、价格为 $W_i$ 的收费公路 $i$。在提价前，存在唯一的收费公路集合，使得可以在任意两个城市间通行且总支付费用最小。

输出格式

如果国王的计划可以实现，则输出一个整数，表示实现国王计划所需的最小总提价幅度。否则，在一行中输出 $-1$。

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

9

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

-1

5 10
1 2 14
1 3 14
1 4 9
1 5 15
2 3 8
2 3 10
2 4 13
3 4 8
4 5 10
4 5 15

21

提示

样例输入/输出 #1 的解释

在提价前，游客会选择收费公路 $1$、$4$ 和 $6$ 来通行。通过将收费公路 $1$、$4$ 和 $6$ 的价格提高到 $6$，游客将使用收费公路 $2$、$3$ 和 $5$ 来通行。收费公路的总提价幅度为 $(6 - 2) + (6 - 3) + (6 - 4) = 9$。

样例输入/输出 #2 的解释

在提价前，游客会选择收费公路 $1$ 和 $2$。无论提价多少，游客总是至少会选择这两条收费公路中的一条。

翻译由 DeepSeek 完成