翻译

在2009年和2010年ICPC世界总决赛期间，该比赛通过万维网进行了网络播出。看到这一点，来自Ajobdesh的一些比赛组织者决定，他们将为Ajobdesh的每所大学提供他们的比赛直播。组织者已决定，他们将为他们提供最好的服务。但是有两个问题：

1.大学之间没有现有的网络。因此，他们需要建立一个新的网络。然而，他们可以在建设网络支付的最高金额为$C$。

2.网络中的每个链路都有带宽。如果流的带宽超过链路的任何可用带宽，则通过该链路连接的查看者无法查看该流。

由于用于流式传输的协议，观众可以从恰好一个其他用户（或组织比赛的服务器）接收流。也就是说，如果您有两个128kbps链路，则不会获得256kbps带宽，但是，如果您有128kbps的流，则可以在该带宽上传输给任意数量的用户。

给定$C$，您必须为所有用户最大化最小带宽。

第一行输入包含$T(≤50)$，测试数据数。接下来是T测试数据。

每个测试数据从一个整数开始$N,M,C(1≤N≤60,1≤M≤10^4, 1≤C≤10^9)$，表示大学的数量，链路的数目，以及设定网络的预算。每个大学都由$0$到$N -1$ 之间的整数标识，其中$0$是服务器。

接下来的M行，每行包含4个整数，$u,v,b,c(0≤u,v <N,1≤b,c≤10^6,u$ !=$V)$ ，描述一个链路从大学$u$到大学$v$，具有$b$ kbps 带宽和成本$c$的带宽。所有链路都是单向的。

每个测试数据之前都有一个空行。

对于每个测试数据，输出流的最大带宽。如果不可能，则输出 “streaming not possible.”