题目描述

贝尔兰有 $N$ 座城市和 $M$ 家国内航空公司，共有 $K$ 条航线。所有这些航空公司实际上都属于 Don Berlione。

由于过去反垄断政策的限制，Don Berlione 不得不把航线分散到不同的航空公司名下。现在限制已经解除，他决定关闭除一家之外的所有航空公司。

最终保留下来的航空公司必须能够仅利用自己拥有的航线，使任意两座城市之间都可以通过若干次中转互相到达。

为了达到这个目的，Don Berlione 可以把其他航空公司的某些航线转交给最终保留的航空公司。虽然这些公司都属于他，但每转让一条航线，仍然需要向政府缴纳一定的税款。

对于每条航线，已知：

• 它连接的两座城市；
• 当前所属的航空公司；
• 将它转让给另一家航空公司所需缴纳的税款。

Don Berlione 可以任意选择一家航空公司保留下来，并将其他公司的若干条航线转让给它。

请计算，为了使最终保留的航空公司能够连通全部 $N$ 座城市，最少需要缴纳多少税款。

输入格式

第一行包含三个整数 $N,M,K$，分别表示城市数量、航空公司数量和航线数量。

满足：

$1\le N\le2000$，

$1\le M\le2000$，

$0\le K\le200000$。

接下来 $K$ 行，每行包含四个整数

$a_i\ b_i\ c_i\ p_i$，

表示第 $i$ 条航线：

• 连接城市 $a_i$ 和城市 $b_i$；
• 当前属于第 $c_i$ 家航空公司；
• 如果将这条航线转让给其他航空公司，需要缴纳 $p_i$ 的税款。

满足：

$1\le a_i,b_i\le N$，且 $a_i\ne b_i$；

$1\le c_i\le M$；

$1\le p_i\le100000$。

两座城市之间可能存在多条航线。

保证如果允许使用所有航空公司的全部航线，那么整个城市网络是连通的。

输出格式

输出一个整数，表示使某一家航空公司能够连通全部城市所需要缴纳的最小总税款。

样例

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

5

样例说明

选择保留第 $2$ 家航空公司。

它原本拥有航线 $(4,3)$ 和 $(1,2)$，再将连接城市 $1$ 和 $3$ 的航线转让给它，需要缴纳 $5$ 的税款。

此时四座城市全部连通，因此答案为 $5$。