template<typename T> inlinevoidread(T &num){ T x = 0, f = 1; char ch = getchar(); for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1; for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0'); num = x * f; }
int n, m, F;
structedge{ int u, v, c, t; double val; booloperator < (const edge b) const { return val < b.val; } } e[10005];
int fa[405]; intfind(int x){ return fa[x] == x ? x : fa[x] = find(fa[x]); } boolcheck(double k){ for (int i = 1; i <= n; i++) fa[i] = i; for (int i = 1; i <= m; i++) { e[i].val = e[i].c * 1.0 + k * e[i].t; } sort(e + 1, e + m + 1); double ret = 0; for (int i = 1; i <= m; i++) { int tx = find(e[i].u), ty = find(e[i].v); if (tx != ty) { ret += e[i].val; fa[ty] = tx; } } return ret < F; }
intmain(){ read(n); read(m); read(F); for (int i = 1; i <= m; i++) { read(e[i].u); read(e[i].v); read(e[i].c); read(e[i].t); } double l = 0, r = 2e9, mid = 0; while (r - l > 1e-7) { mid = (l + r) / 2; if (check(mid)) { l = mid + 0.000001; } else r = mid - 0.000001; } printf("%.4lf\n", l); return0; }