import java.util.PriorityQueue fun dijkstra(g: List>>, start: Int) : DoubleArray { val d = DoubleArray(g.size) { Double.MAX_VALUE / 2 } d[start] = 0.0 val q = PriorityQueue>(compareBy {it.first}) val used = BooleanArray(g.size) { false } q.add(0.0 to start) while (q.isNotEmpty()) { val (_, v) = q.poll() if (used[v]) continue used[v] = true for ((u, l) in g[v]) { if (!used[u] && d[u] > d[v] + l) { d[u] = d[v] + l q.add(d[u] to u) } } } return d } fun main() { val (n, m, t) = readInts() val g1 = List(n) { mutableListOf>() } val g2 = List(n) { mutableListOf>() } repeat(m) { val (x, y, l, v, w) = readInts() g1[x - 1].add(y - 1 to (l.toDouble() / v)) g2[x - 1].add(y - 1 to (l.toDouble() / w)) g1[y - 1].add(x - 1 to (l.toDouble() / v)) g2[y - 1].add(x - 1 to (l.toDouble() / w)) } val dist1 = dijkstra(g1, 0) val dist2 = dijkstra(g2, n - 1) var ans = dist1[n - 1] for (v in 0 until n) { if (dist1[v] > t) continue for ((e1, e2) in g1[v].zip(g2[v])) { val (u, t1) = e1 val (_, t2) = e2 val part = (t - dist1[v]) / t1 ans = minOf(ans, maxOf(dist1[v] + t1 * part, t.toDouble()) + maxOf(0.0, t2 * (1.0 - part)) + dist2[u]) } } println(ans) } private fun readInt() = readln().toInt() private fun readLongs() = readStrings().map { it.toLong() } private fun readStrings() = readln().split(" ") private fun readInts() = readStrings().map { it.toInt() }