{"problem":{"name":"[JOIST 2022] 复兴计划 / Reconstruction Project","description":{"content":"JOI 镇是一个曾经辉煌的工业区。为了运输产品，其中建起了许多铁轨与火车站。尽管 JOI 镇已经衰落，那里仍有许多不再被使用的铁轨与火车站。 JOI 镇中有 $N$ 个火车站，编号为 $1,2,\\dots,N$。其中还剩下 $M$ 条铁轨。第 $i$ 条铁轨 $(1\\le i \\le M)$ 双向连接火车站 $A_i$ 和 $B_i$，且其宽度为 $W_i$。保证能够从任意火车站经过若干条铁轨到","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":5000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9531"},"statements":[{"statement_type":"Markdown","content":"JOI 镇是一个曾经辉煌的工业区。为了运输产品，其中建起了许多铁轨与火车站。尽管 JOI 镇已经衰落，那里仍有许多不再被使用的铁轨与火车站。\n\nJOI 镇中有 $N$ 个火车站，编号为 $1,2,\\dots,N$。其中还剩下 $M$ 条铁轨。第 $i$ 条铁轨 $(1\\le i \\le M)$ 双向连接火车站 $A_i$ 和 $B_i$，且其宽度为 $W_i$。保证能够从任意火车站经过若干条铁轨到达任意其他火车站。\n\n你是 JOI 镇的镇长。你计划吸引铁路公司来使用 JOI 镇中留下的铁轨与火车站，使得 JOI 镇复苏成为「铁路之镇」。 \n \n于是，共有 $Q$ 个铁路公司申请参与这个复兴计划。然而，不同公司的火车所需的铁轨宽度也有所不同。这意味着你需要重建这些铁轨，使得它们都匹配对应公司的火车。 \n\n第 $j$ $(1\\le j\\le Q)$ 家铁路公司的火车所需的铁轨宽度为 $X_j$。为了迎合公司 $j$，要求满足以下条件：\n- **条件**：保证能够从任意火车站只经过宽度为 $X_j$ 的铁轨到达任意其他火车站。\n\n为了满足上述条件，你可以按如下方式重建铁轨任意次：\n- **重建**：选择一条铁轨，你可以重建其使得其宽度增加或减少 $1$ 并花费 $1$。然而，若其宽度为 $1$，则不能再减少其宽度。\n\n为了确定你能满足哪些公司，你需要求出迎合公司 $j$ 所需要的最小花费。\n\n请写一个程序，对于给定的火车站、铁轨与铁路公司的信息，计算迎合公司 $j$ 所需要的最小花费。\n\n## Input\n\n第一行，两个正整数 $N,M$，表示火车站的个数和铁轨的条数。\n\n接下来 $M$ 行，其中第 $i$ $(1 \\le i \\le M)$ 行包含三个正整数 $A_i, B_i, W_i$，表示第 $i$ 条铁轨连接的火车站和其宽度。\n\n第 $M+2$ 行，一个正整数 $Q$，表示铁路公司的个数。\n\n接下来 $Q$ 行，其中第 $j$ $(1 \\le j \\le Q)$ 行包含一个正整数 $X_j$，表示第 $j$ 个铁路公司的火车需要的铁路宽度。\n\n## Output\n\n输出 $Q$ 行，第 $j$ $(1\\le j\\le Q)$ 包含一个整数，表示迎合公司 $j$ 所需要的最小花费。\n\n[samples]\n\n## Background\n\nJOISC2022 D4T3\n\n## Note\n\n**【样例解释 #1】**\n\n例如，为了迎合公司 $1$，若你按如下方式重建铁轨，将会花费 $8$。\n\n1. 将铁轨 $6$ 的宽度减少 $4$。\n2. 将铁轨 $9$ 的宽度减少 $3$。\n3. 将铁轨 $10$ 的宽度增加 $1$。\n\n可以证明不可能用少于 $8$ 的花费迎合公司 $1$。因此，在第一行输出 $8$。\n\n该样例满足子任务 $1,2,4,5,6$ 的限制。\n\n**【样例解释 #2】**\n\n该样例满足所有子任务的限制。\n\n**【样例解释 #3】**\n\n该样例满足子任务 $2,4,5,6$ 的限制。\n\n**【数据范围】**\n\n对于所有数据，满足：\n\n- $2 \\le N \\le 500$。\n- $N-1 \\le M \\le 100\\,000$。\n- $1 \\le Q \\le 1\\,000\\,000$。\n- $1 \\le A_i < B_i \\le N$ $(1\\le i\\le M)$。\n- $1 \\le W_i \\le 10^9$ $(1\\le i\\le M)$。\n- $(A_i,B_i,W_i)\\ne(A_j,B_j,W_j)$ $(1\\le i<j\\le M)$。\n- 保证能够从任意火车站经过若干条铁轨到达任意其他火车站。\n- $1 \\le X_j \\le 10^9$ $(1\\le j\\le Q)$。\n- $X_j < X_{j+1}$ $(1\\le j<Q)$。\n\n详细子任务附加限制及分值如下表所示：\n\n|子任务编号|附加限制|分值|\n|:-:|:-:|:-:|\n|$1$|$M \\le 16$，$Q \\le 10$|$3$|\n|$2$|$Q\\le 10$|$4$|\n|$3$|$B_i = A_i+1$ $(1\\le i\\le M)$|$7$|\n|$4$|$M\\le 1\\,000$|$28$|\n|$5$|$Q\\le 20\\,000$|$35$|\n|$6$|无附加限制|$23$|","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9531","tags":["2022","O2优化","JOISC/JOIST（日本）"],"sample_group":[["5 10\n1 2 8\n1 3 13\n1 4 5\n1 5 11\n1 5 3\n2 3 7\n2 4 15\n3 4 6\n3 5 6\n4 5 2\n6\n3\n6\n8\n10\n13\n17","8\n2\n5\n10\n9\n21"],["3 4\n1 2 1\n1 2 4\n2 3 2\n2 3 4\n4\n1\n2\n3\n4","1\n1\n2\n0"],["10 20\n6 7 914727791\n1 8 771674531\n3 5 632918108\n5 9 329296846\n1 7 237501112\n4 9 303328173\n2 6 216298255\n2 10 504024991\n3 8 158236886\n1 10 10176179\n8 9 918271145\n3 6 217165898\n3 6 624543444\n4 9 70147274\n8 9 976983490\n6 9 210108505\n2 9 972711062\n1 10 564567289\n3 7 411395464\n4 7 952470985\n10\n115721165\n198969744\n356664401\n429802521\n513343279\n610443927\n741016686\n786597783\n898772266\n903568946","1121073688\n761832468\n1026806785\n1316097872\n1321500065\n1445238392\n1637513141\n1621778548\n1733953031\n1738749711"]],"created_at":"2026-03-03 11:09:25"}}