import java.util.* import kotlin.math.abs fun main() { val (n, m, t) = readln().split(" ").map { it.toInt() } val graph = System.`in`.bufferedReader().lineSequence().take(m) .flatMap { line -> val (a, b, l, v) = line.split(" ").map { it.toInt() } // add reverse connections too listOf(a to (b to (l to v)), (b to (a to (l to v)))) }.groupBy({ it.first }) { it.second } // check 0 case first fun dijkstra(mid: Double): Double { val distances = DoubleArray(n + 1) { Double.MAX_VALUE } distances[1] = 0.0 val queue = PriorityQueue>(Comparator.comparingDouble { it.second }) queue.add(1 to 0.0) while (queue.isNotEmpty()) { val (location, cost) = queue.poll() // don't continue on more expensive paths if (cost > distances[location]) continue graph[location]!! .map { (b, v) -> b to (cost + v.first / (v.second + mid)) } // Update distances .forEach { (b, c) -> // corner cases, multiple paths to the same node if (c < distances[b]) { distances[b] = c queue.add(b to c) } } } return distances[n] } if (dijkstra(0.0) < t) return println(0.0) // Binary search var low = 0.0 var high = 1e10 while (abs(high - low) > 1e-6) { val mid = (low + high) / 2 // dijkstra val result = dijkstra(mid) if (result > t) low = mid else high = mid } println(low) }