{"problem":{"name":"「HGOI-1」Build","description":{"content":"这个小镇将要和周围的其他小镇一共 $n$ 个小镇，一起修建一个能**连通**这 $n$ 个小镇，有 $m$ 条高速公路的交通网。其中每条高速公路都将会连接**不同的两个小镇**，即不存在一条高速公路的起点和终点相同。 但高速公路的修建费用是很高的，所以镇长们一致决定将共同承担高速公路的费用，所以他们希望修建的**总费用最小**。 而且由于不同小镇的基础设施建设情况不同，所以每个小镇在修建的费用","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8483"},"statements":[{"statement_type":"Markdown","content":"这个小镇将要和周围的其他小镇一共 $n$ 个小镇，一起修建一个能**连通**这 $n$ 个小镇，有 $m$ 条高速公路的交通网。其中每条高速公路都将会连接**不同的两个小镇**，即不存在一条高速公路的起点和终点相同。\n\n但高速公路的修建费用是很高的，所以镇长们一致决定将共同承担高速公路的费用，所以他们希望修建的**总费用最小**。\n\n而且由于不同小镇的基础设施建设情况不同，所以每个小镇在修建的费用也不同。经过协商，每条高速公路将由其所连接的两个小镇共同施工。每个小镇负责一半路程。为了同时结束整个施工过程，显然将会有小镇同时进行多条道路的施工，而施工的道路数量越多，所需要花费的价钱就越多。\n\n经过计算，每个小镇施工的花费可以用函数表示，及对于小镇 $i$，有三个参数 $a_i$，$b_i$，$c_i$。对于 $i$ 小镇来说在修建其第 $j$ 条高速时，**这条**高速所需要的花费为 $a_ij^2+b_ij+c_i$。\n\n现在，这些镇长想要 $\\text{uuku}$ 给他们提供一个满足要求的**建造方案**，使**总价格最小**。\n\n当然，$\\text{uuku}$ 将这个问题交给了你。\n\n## Input\n\n第一行两个整数 $n$，$m$。\n\n接下来 $n$ 行，每行三个整数 $a_i$，$b_i$，$c_i$。\n\n## Output\n\n共 $m+1$ 行\n\n第一行一个整数表示最小价格。\n\n接下来 $m$ 行，每行两个整数 $u$，$v$，表示你提供的方案中的一条边。\n\n[samples]\n\n## Background\n\n一次旅行，$\\text{uuku}$ 到了一个奇怪的小镇。\n\n## Note\n\n#### 数据范围\n本题采用**捆绑测试**，共有 $6$ 个 $\\text{subtask}$，最终分数为所有 $\\text{subtask}$ 分数之和。\n$$\n\\def\\arraystretch{1.5}\n\\begin{array}{|c|c|c|}\\hline\n\\textbf{Task} & \\textbf{Score} & \\textbf{特殊限制} \\cr\\hline\n1 & 10 & n,m\\le 500  \\cr\\hline\n2 & 20 &  n,m\\le 5\\times 10^3 \\cr\\hline\n3 & 10 & \\text{每个小镇的函数相同}\\cr\\hline\n4 & 20 & a_i=0 \\cr\\hline\n5 & 20 & m=n-1 \\cr\\hline\n6 & 20 & \\cr\\hline\n\\end{array}\n$$\n\n对于 $100\\%$ 的数据，$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$。\n\n数据保证最小价格在 $\\tt{long \\ long}$ 范围内。\n\n#### 说明\n\n本题有 $\\text{spj}$，价格正确可以获得 $30\\%$ 的分数。每个 $\\text{subtask}$ 取其中所有数据点得分的最小值。\n\n如果你不会构造方案，也请你再输出最小价格后输出 $m$ 行，每行两个 $[1,n]$ 范围内的整数，防止 $\\text{spj}$ 出现错误。\n\n本题已添加 hack 数据，为 $\\text{subtask7}$，该 $\\text{subtask}$ 不计分数，但会影响是否 $\\text{AC}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8483","tags":["图论","贪心","二分","堆","洛谷原创","Special Judge","O2优化","构造","洛谷月赛"],"sample_group":[["4 4\n1 2 3\n2 3 4\n3 4 5\n4 5 6","114\n1 2\n1 2\n1 3\n3 4"]],"created_at":"2026-03-03 11:09:25"}}