模板洛谷P4951
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=410,M=1e4+10;
const double eps=1e-6;
typedef long long LL;
struct edge{LL u,v,c,t;
}e[M];
LL n,m,f;
int fa[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);
}
bool check(double k){for(int i=1;i<=n;i++){fa[i]=i;}sort(e+1,e+m+1,[&](edge& x,edge& y){return x.t*k+x.c<y.t*k+y.c;});double sum=0;for(int i=1;i<=m;i++){int u=e[i].u,v=e[i].v;int t=e[i].t,c=e[i].c;int fu=find(u);int fv=find(v);if(fu==fv)continue;sum+=k*t+c;fa[fu]=fv;}return f-sum>=eps;
}int main(){// cin.tie(nullptr)->sync_with_stdio(false);cin>>n>>m>>f;for(int i=1;i<=m;i++){cin>>e[i].u>>e[i].v>>e[i].c>>e[i].t;}double l=0,r=f;while(r-l>eps){double mid=(l+r)/2;if(check(mid))l=mid;elser=mid;}printf("%.4lf\n",l);return 0;
}