Tree

题目描述

给你一个无相带权连通图，每条边是黑色或白色，让你求一棵最小权的恰好有need条白色边的生成树。题目保证有解。

输入

第一行V，E，need分别表示结点数、边数和需要的白色边数。

接下来E行，每行s，t，c，col分别表示这边的两个端点（结点从0开始标号），边权，颜色（0表示白色，1表示黑色）。

输出

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

V≤50000，E≤100000，所有数据边权为[1,100]中的正整数。

样例

来源

一本通