黑白之树

题目描述

给出一个包含$n$个点$m$条边的无向带权连通图，点的编号为$0$，$1$，$\ldots$，$n-1$，每条边是黑色或白色。

请你求一棵最小权的恰好有$k$条白色边的生成树。题目保证有解。

输入格式

第一行$n$，$m$，$k$分别表示点数，边数和需要的白色边数。

接下来$m$行，每行$u$，$v$，$w$，$col$表示这边的端点，边权，颜色（$0$表示白色，$1$表示黑色）。

输出格式

仅一行，表示所求生成树的边权和。

数据范围与提示

对于$100\%$的数据，$1 \leq n \leq 5 \times 10^{4}$，$0 \leq m \leq 10^{5}$，边权为$[1,100]$中的正整数。

样例

2 2 1
0 1 1 1
0 1 2 0

2