题目描述

有 $n$ 名管理员和 $m$ 条双向通信渠道，需要让全部管理员直接或间接连通。

渠道分为两类：必选渠道必须全部选择，可选渠道可以按需选择。请在满足全部要求的前提下，使总费用尽可能小。即使必选渠道形成环、同一对管理员之间存在多个必选渠道，这些渠道的费用也必须全部支付。

输入格式

第一行两个整数 $n,m$。接下来 $m$ 行，每行四个整数 $p,u,v,w$。$p=1$ 表示必选渠道，$p=2$ 表示可选渠道，$u,v$ 是两端管理员的编号，$w$ 是费用。

输出格式

输出最小的总通信费用。

样例

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

9

数据范围

• 对于 $30\%$ 的数据，$n\le10$，$m\le100$。
• 对于 $50\%$ 的数据，$n\le200$，$m\le1000$。
• 对于 $100\%$ 的数据，$1\le n\le2000$，$0\le m\le10000$，$0\le w\le100000$。

保证所有给出的渠道能够连通全部管理员。允许同一对管理员之间有多条渠道。