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

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

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

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

国王请你计算实现这一计划所需的最小总涨价幅度，或者报告无法实现该计划。

输入格式

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

输出格式

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

样例

输入 1

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

输出 1

9

说明 1

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

输入 2

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

输出 2

-1

说明 2

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

输入 3

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

输出 3

21