← 返回题目列表

AtCoder · asaporo_c

A. 图表

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

Takahashi 发现了一个无向连通图 N 顶点和 M 边缘。顶点已编号 1 通过 N。的 i第一条边连接顶点 a_i 和 b_i,重量为 c_i.

他会打 Q 使用此图表的游戏轮次。在 i第一轮,两个顶点 S_i 和 T_i 被指定,他将选择边的子集,使得可以从至少一个顶点到达任何顶点 S_i or T_i 通过遍历选定的边。

对于每一轮,找到 Takahashi 选择的边的最小可能总重量。

约束

  • 1 ≦ N ≦ 4,000
  • 1 ≦ M ≦ 400,000
  • 1 ≦ Q ≦ 100,000
  • 1 ≦ a_i,b_i,S_i,T_i ≦ N
  • 1 ≦ c_i ≦ 10^{9}
  • a_i \neq b_i
  • S_i \neq T_i
  • 给定的图形已连接。

部分分数

  • 在测试集中值得 200 点, Q = 1.
  • 在测试集中值得另一个 300 点, Q ≦ 3000.

输入

输入由标准输入按以下格式给出:

N M
a_1 b_1 c_1
a_2 b_2 c_2
:
a_M b_M c_M
Q
S_1 T_1
S_2 T_2
:
S_Q T_Q

输出

打印 Q 行。的 i第行应包含 Takahashi 选择的边的最小可能总权重。


示例输入 1

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

示例输出 1

8
7

我们将检查每一轮:

  • 在 1-st 回合,选择边缘 1 和 3 达到最小总重量 8.
  • 在 2- 第二轮,选择边缘 1 和 2 达到最小总重量 7.

示例输入 2

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

示例输出 2

8

此输入满足两个部分分数的附加约束。