A. 子图

题目描述

小W有一张 $n$ 个点 $m$ 条边的无向图 $\lt V,E\gt $，其中 $V$ 为点集，$E$ 为边集，但是他不太喜欢这张图。小W认为他喜欢一张图，当且仅当对于任意点集的子集 $V' \subseteq V$ 满足对于集合 $E' = \{ (u,v) | (u,v) \in E, u, v \in V'\}$ ，有 $|E'| \lt |V'|$ 。如果你有公式恐惧症，上面的题意就是说对于这个图的任意一些点，这些点之间互联的边数小于这些点的总点数。

小W想要删掉一些边，使得这张图是他喜欢的。但是删边是有代价的，他想要最小化他所要删的边的总代价。

输入格式

第一行两个整数 $n$，$m$。

接下来 $m$ 行，每行三个整数 $u$，$v$，$c$，表示有一条 $u$ 和 $v$ 之间连接的边，删掉这条边的代价是 $c$。

输出格式

输出一行表示最小的总代价。

样例1

input

4 4
1 2 1
2 3 2
3 4 3
4 1 4

output

1

限制与约定

对于 $10\%$ 的数据，$n , m \le 10$。

对于 $40\%$ 的数据，$n, m \le 1000$。

对于另外 $20\%$ 的数据，$c = 1$。

对于 $100\%$ 的数据，$n, m \le 5 * 10^5, 1 \le u, v \le n, 1 \le c \le 10^9$。

时间限制：1s

空间限制：512MB

提示

输入输出量可能很大，请使用较快的I/O方式。

下载

样例数据下载