单点时限: 2.0 sec
内存限制: 256 MB
在 A 国有很多城际铁路。这些铁路都连接两个城市（城市从 $1$ 到 $n$ 编号），可以双向通行，使得任意两个城市之间都由铁路网联系起来。
不过在一次星球大战之后，所有的铁路都经历了不同程度的损伤以至于无法通行了。由于经费紧缺，A 国政府不愿意再出资造新的铁路。对于原有的城际铁路，根据铁路的实际情况，有以下两种处理办法：
A国政府修复铁路的总预算是 $M$，目标是要让任意两个城市之间都能通过铁路联系起来。在预算不够且能够完成目标的条件下，显然没必要修复每一条铁路。
国外公司通过不知什么途径了解到了 A 国政府的总预算 $M$，他们现在要把 $k$ 定下来，并且希望 $k$ 尽可能得大。但 $k$ 又不能太大，不然，如果 A 国政府发现无法完成任务的话，整个订单都会泡汤。
测试数据包含不超过 30 个测试文件。每个测试文件是单个测试点。
第一行是三个整数 $n, m, M$ $(2 \leq n \leq 10^5, n-1 \leq m \leq \min {10^5, \frac{n(n-1)}{2} }, 1 \leq M \leq 10^{15})$。
接下来 $m$ 行，每行四个整数 $u_i, v_i, t_i, f_i$。表示一条城际铁路，连接着 $u_i$ 和 $v_i$ 城市，$t_i$ 表示铁路实际修复费用。$f_i=1$ 表示只能由国外公司修复，$f_i=0$ 表示由国内公司修复。$(1 \leq u_i, v_i \leq n, u_i \neq v_i, 1 \leq t_i \leq 10^6, f_i \in {0, 1})$。输入保证两个城市之间不会存在多条铁路。
输入保证：
求 $k$ 的最大值。输出答案与标准答案相差不超过 $10^{-6}$ 即判为正确。
3 3 9 1 2 1 1 1 3 2 0 2 3 1 1
7.000000
3 3 9 1 2 1 1 1 3 2 1 2 3 2 1
3.000000