E. Energy crisis
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The European Union is experiencing an energy crisis. Given this situation, the Ministry of Energy of Kazakhstan wants to redesign the network of routes connecting the country's power plants. Kazakhstan has $$$N$$$ power plants scattered across its territory. The Ministry has information on all the routes that connect these plants, as well as the cost involved in maintaining each route. In particular, the cost of maintaining the $$$i$$$-th route varies over time and depends on three parameters $$$a_i$$$, $$$b_i$$$, and $$$c_i$$$, following the function $$$$$$a_it^2 + b_it + c_i,$$$$$$ where $$$t$$$ represents the time.

To carry out this task, the minister has hired Marcel "the Optimizer" Saito. After analyzing Kazakhstan's geography, Marcel already has a plan to redesign the country's route network. However, as this would involve making significant changes, he needs to demonstrate how effective his plan is. To do this, he wants to calculate the minimum cost of connecting all the power plants using the existing routes at a given time $$$t$$$.

Marcel is very busy preparing his newest apprentice, Daniel "the Dynamic" Ito. Therefore, he has assigned this task to you.

Input

The input consists of $$$M + 1$$$ lines. The first line contains two integers $$$N$$$ ($$$2 \leq N \leq 100$$$) and $$$M$$$ ($$$N - 1 \leq M \leq 200$$$), representing the number of power plants and the number of routes between these plants, respectively.

The following $$$M$$$ lines each contain five integers $$$x_i$$$, $$$y_i$$$, $$$a_i$$$ $$$(1 \leq a_i \leq 10^4)$$$, $$$b_i$$$ $$$(-10^4 \leq b_i \leq 10^4)$$$, and $$$c_i$$$ $$$(-10^4 \leq c_i \leq 10^4)$$$ indicating the existence of a route connecting the power plants $$$x_i$$$ and $$$y_i$$$ with a cost over time given by $$$a_it^2 + b_it + c_i$$$. It is guaranteed that:

  • $$$1 \leq x_i, y_i \leq N$$$, $$$x_i \neq y_i$$$,
  • $$$a_it^2 + b_it + c_i \geq 0$$$, for all $$$t \in \mathbb{R}$$$,
  • Using the existing routes, it is possible to travel from any power plant to any other.
Additionally, there is at most one direct route between any pair of power plants.
Output

A single line containing the minimum cost to connect these power plants over time. Your answer is considered correct if the absolute or relative error does not exceed $$$10^{-6}$$$.

Example
Input
3 3
1 2 3 2 1
2 3 4 -3 10
1 3 1 -5 7
Output
7.437500000