#include #include #include using namespace std; const int N = 100500; struct Edge { int u; double ln, v; }; int n, m; double t; vector g[N]; double dijkstra(double x) { vector d(n, -1.0); d[0] = 0; set> q; q.emplace(0.0, 0); while (!q.empty()) { auto [dv, v] = *q.begin(); q.erase(q.begin()); for (const Edge& e : g[v]) { int u = e.u; double du = dv + (e.ln / (e.v + x)); if (d[u] < 0 || d[u] > du) { q.erase(pair(d[u], u)); d[u] = du; q.emplace(du, u); } } } return d[n - 1]; } int main() { ios_base::sync_with_stdio(false); cin >> n >> m >> t; for (int i = 0; i < m; ++i) { int v, u; double ln, s; cin >> v >> u >> ln >> s; v--; u--; Edge eu = {u, ln, s}; g[v].push_back(eu); Edge ev = {v, ln, s}; g[u].push_back(ev); } double lf = 0, rg = 1e18; for (int i = 0; i < 100; ++i) { double mid = (lf + rg) / 2; if (dijkstra(mid) <= t) { rg = mid; } else { lf = mid; } } cout.precision(10); cout << fixed << rg << endl; return 0; }