题目描述

Tyvj 已经一岁了，网站也由最初的几个用户增加到了上万个用户。随着 Tyvj 网站的逐步壮大，管理员的数目也越来越多。现在你身为 Tyvj 管理层的联络员，希望你找到一些通信渠道，使得管理员两两之间都可以联络（直接或者是间接都可以）。Tyvj 是一个公益性的网站，没有过多的利润，所以你要尽可能使总费用最少。

目前你已经知道，Tyvj 的通信渠道分为两大类：一类是必选通信渠道，无论价格多少，你都需要把所有的都选择上；还有一类是选择性的通信渠道，你可以从中挑选一些作为最终管理员联络的通信渠道。数据保证给出的所有通信渠道能够让所有的管理员连通。

输入格式

第一行包含两个整数 $n,m$，表示 Tyvj 一共有 $n$ 个管理员，有 $m$ 个通信渠道。

接下来 $m$ 行，每行包含四个非负整数 $p,u,v,w$：

• 当 $p=1$ 时，表示该通信渠道为必选通信渠道；
• 当 $p=2$ 时，表示该通信渠道为选择性通信渠道。 $u,v$ 表示该渠道连接的管理员编号，$w$ 表示费用。渠道是双向的，即 $u$ 可以收到 $v$ 的信息，$v$ 也可以收到 $u$ 的信息。

输出格式

输出一个整数，表示最小的通信费用。

样例

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

9

数据范围

• 对于 $30\%$ 的数据，$n \le 10$，$m \le 100$；
• 对于 $50\%$ 的数据，$n \le 200$，$m \le 1000$；
• 对于 $100\%$ 的数据，$n \le 2000$，$m \le 10000$。
• 注意：$u,v$ 之间可能存在多条通信渠道，你的程序应该累加所有 $u,v$ 之间的必选通信渠道的费用。