P15627 [ICPC 2022 Jakarta R] Increase the Toll Fees

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$。

#### 样例输入/输出 #1 的解释 在提价前，游客会选择收费公路 $1$、$4$ 和 $6$ 来通行。通过将收费公路 $1$、$4$ 和 $6$ 的价格提高到 $6$，游客将使用收费公路 $2$、$3$ 和 $5$ 来通行。收费公路的总提价幅度为 $(6 - 2) + (6 - 3) + (6 - 4) = 9$。 #### 样例输入/输出 #2 的解释 在提价前，游客会选择收费公路 $1$ 和 $2$。无论提价多少，游客总是至少会选择这两条收费公路中的一条。 翻译由 DeepSeek 完成