Time Is Money

A telecom company wants to bring broadband internet to $N$ towns. To do so it is enough to build a network of $N-1$ broadband links between the towns so that a message can travel from any town to every other town.

Every pair of towns that can be directly linked is already known, and for each possible link the company knows the cost to build it and the time it takes to build it.

The company wants to minimize both the total build time (links are built one at a time, so the times add up) and the total money spent. Unable to choose between the two criteria, it evaluates a network with the following formula:

• $\text{SumTime}$ = the sum of the build times of the chosen links
• $\text{SumMoney}$ = the sum of the costs of the chosen links
• $V = \text{SumTime} \times \text{SumMoney}$

Choose the $N-1$ links to build so that the value $V$ is minimized.

The first line contains two integers $N$ (the number of towns) and $M$ (the number of pairs of towns that can be directly connected). Towns are numbered from $0$ to $N-1$.

Each of the next $M$ lines contains four integers $x$, $y$, $t$, and $c$, meaning that town $x$ and town $y$ can be connected with build time $t$ and cost $c$.

It is guaranteed that the given links allow all towns to be connected.

Print a single integer: the minimum possible value of $V = \text{SumTime} \times \text{SumMoney}$.

• $1 \le N \le 200$
• $1 \le M \le 10,000$
• $0 \le x, y \le N-1$
• $1 \le t, c \le 255$
• One test case satisfies $M = N - 1$.