Background

On a trip, $\text{uuku}$ arrived at a strange small town.

Problem Description

This town, together with the surrounding towns, plans to build a transportation network for a total of $n$ towns, with $m$ highways, that can connect all $n$ towns. Each highway will connect two different towns, meaning there will be no highway whose start and end are the same town.

However, building highways is expensive, so the mayors decided to share the cost. They want the total cost to be minimal.

Also, because different towns have different infrastructure, the construction cost differs by town. After negotiation, each highway will be built jointly by the two towns it connects, with each town responsible for half of the road. To finish the whole construction process at the same time, it is clear that a town may work on multiple roads at once, and the more roads it builds, the more money it needs to pay.

After calculation, the construction cost of each town can be described by a function. For town $i$, there are three parameters $a_i$, $b_i$, $c_i$. For town $i$, when building its $j$-th highway, the cost required for this highway is $a_ij^2 + b_ij + c_i$.

Now, the mayors want $\text{uuku}$ to provide a construction plan that meets the requirements and makes the total cost minimal.

Of course, $\text{uuku}$ passed this problem on to you.

Input Format

The first line contains two integers $n$, $m$.

The next $n$ lines each contain three integers $a_i$, $b_i$, $c_i$.

Output Format

There are $m+1$ lines in total.

The first line contains one integer, the minimal cost.

The next $m$ lines each contain two integers $u$, $v$, representing an edge in your plan.

4 4
1 2 3
2 3 4
3 4 5
4 5 6

114
1 2
1 2
1 3
3 4

Hint

Constraints

This problem uses bundled testdata. There are $6$ $\text{subtask}$ in total, and the final score is the sum of the scores of all $\text{subtask}$.

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{Task} & \textbf{Score} & \textbf{Special Constraints} \cr\hline 1 & 10 & n,m\le 500 \cr\hline 2 & 20 & n,m\le 5\times 10^3 \cr\hline 3 & 10 & \text{All towns have the same function}\cr\hline 4 & 20 & a_i=0 \cr\hline 5 & 20 & m=n-1 \cr\hline 6 & 20 & \cr\hline \end{array}$$

For $100\%$ of the data, $2\le n \le 2 \times 10^5$, $n-1 \le m \le 10^6$, $0 \le a_i$, $b_i$, $c_i \le 10^6$.

The data guarantees that the minimal cost fits in $\tt{long \ long}$.

Notes

This problem has an $\text{spj}$. If the cost is correct, you can get $30\%$ of the score. For each $\text{subtask}$, the score is the minimum among all test points in that $\text{subtask}$.

If you do not know how to construct a plan, after outputting the minimal cost, you should still output $m$ lines, each with two integers in the range $[1,n]$, to prevent the $\text{spj}$ from failing.

Hack data has been added as $\text{subtask7}$. This $\text{subtask}$ does not count toward the score, but it will affect whether you get $\text{AC}$.

Translated by ChatGPT 5