题目描述

某岛国，有 $N$ 个城市。作为该国的基础设施，这些城市之间，有 $M$ 条通讯线路。利用这些通讯线路，所有城市之间都是可以通信联络的。不幸的事情发生了，一场暴风雪之后，有些通讯线路被破坏了。经过排查，上报汇总了所有 $M$ 条通讯线路状况信息：是否完好？若被破坏，修复的代价几何？

当务之急是要用最小的成本，尽快抢修一部分通讯线路，恢复该国通信联络，确保该国所有城市都联通。

输入格式

第一行，两个整数 $N$ 和 $M$。
接下来 $M$ 行，每行有 $4$ 个正整数：$0\ u\ v\ w$ 或者 $3$ 个正整数：$1\ u\ v$。

• $4$ 个正整数：$0\ u\ v\ w$ 表示 $u$ 到 $v$ 的通讯线路被破坏，修复的代价为 $w$。
• $3$ 个正整数：$1\ u\ v$ 表示 $u$ 到 $v$ 的通讯线路完好。

输出格式

一个整数，意义如题所述，表示恢复所有城市通讯联络的最小代价。

样例

输入数据 #1

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

输出数据 #1

5

解释 #1

修复第 $6$ 条线路。

数据范围

20% 数据 $m = n-1$

$1 \leq N \leq 2000$
$M \leq 10000$
$1 \leq u, v \leq N$
$1 \leq w \leq 10000$