Minimizing Total Burning Time

The fireworks display is about to conclude, and in order to leave a memorable impression, Cuixiang has devised a spectacular experiment. She has prepared a device consisting of three components:

• Ropes of length 1
• Ropes of length \(\sqrt{2}\)
• A non‐burnable board that is partitioned into unit cells with grid vertices

The ropes are placed on the board such that each rope’s endpoints lie exactly on the grid vertices. In particular, a rope of length 1 can only be placed along an edge of a cell, and a rope of length \(\sqrt{2}\) may only be placed along a diagonal of a cell. All ropes are connected to form a connected graph (i.e. any two points on the ropes can reach each other via some sequence of ropes).

The trick is that the fire is ignited at one of the rope endpoints (and never in the middle of a rope). Once ignited, the fire travels along the rope at its own burning speed, and upon reaching an endpoint it ignites all ropes connected there. Note that if an edge is being burned from both ends, the two fire fronts will meet somewhere in the middle and the rope will finish burning earlier. In fact, for a rope (edge) connecting vertices \(u\) and \(v\) with burning speed \(s\) and length \(L\) (either \(1\) or \(\sqrt{2}\)), if the fire reaches vertices \(u\) and \(v\) at times \(t_u\) and \(t_v\) respectively, then the rope will completely burn at time

\(T_{edge} = \frac{L/s + t_u + t_v}{2}\).

The vertices become ignited in a standard fashion: if an ignited vertex \(u\) is connected to vertex \(v\) by a rope, then the fire will reach \(v\) at time \(t_u + L/s\) (unless \(v\) is ignited earlier from another rope).

Your task is to determine the optimal vertex at which to start the fire so that the overall time by which all ropes are burned is minimized. In other words, if you choose a starting vertex \(r\) and let \(d(v)\) be the time at which vertex \(v\) gets ignited (computed as the shortest path from \(r\) with edge weights defined as \(L/s\)), then the finishing time of an edge \((u,v)\) is \(\frac{L/s+d(u)+d(v)}{2}\) and the total burn time is the maximum such time over all edges. You must choose \(r\) to minimize this value.

Can you help Cuixiang achieve the perfect show? If you do, not only will you earn 100 points, but you will also be treated to a grand fireworks display!

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \leq n \leq 10^3\), \(1 \leq m \leq 10^4\)), representing the number of vertices and the number of ropes (edges) respectively. The following \(m\) lines each contain four values: \(u\), \(v\), type, and \(s\).

• \(u\) and \(v\) (1-indexed) are the endpoints of the rope.
• type is either 1 or 2. If type = 1, the rope has length 1; if type = 2, the rope has length \(\sqrt{2}\).
• \(s\) is a positive integer representing the burning speed of that rope.

The graph is guaranteed to be connected.

outputFormat

Output the minimal total time required to burn all the ropes. The answer should be printed with exactly 6 decimal places.

Recall that for a rope (edge) with length \(L\) and burning speed \(s\), and with its endpoints ignited at times \(t_u\) and \(t_v\), its complete burning time is computed as:

\(\displaystyle T_{edge} = \frac{L/s + t_u + t_v}{2}\).

sample

4 4
1 2 1 1
2 3 1 1
3 4 1 1
4 1 1 1

2.000000