UOJ Logo

NOI.AC

#39. 子图

统计

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方式。

下载

样例数据下载