問題文
高桥在游戏中统治国家。
为了国家 N 城市和M 有一条书路。每条路径都是 2 它直接连接两个不同的城市,沿途没有其他城市。另外,哪个 2 即使对于两个城市来说,也没有直接连接它们的道路。 1 一。
起初,所有道路都没有铺好,所有城市都没有贸易站。
高桥决定为国家的发展铺路、建立贸易站。
如果任何城市满足以下任何条件,则称一个国家处于“良好状况”。
- 城市中有一个贸易站。
- 虽然一个城市没有贸易站,但可以从该城市前往另一个有贸易站的城市,但只能通过铺好的道路。
在城市 1 如果要将其更改为输出最多为 N 在路上直到 它们的编号最大为 1 如果要将其更改为输出最多为 M 。城市 在 i 设立交易站需要金币。 需要 c_i 页。还有,路 需要金币才能铺好 i 需要 r_i 页。
我没有很多金币,所以我想尽量减少让国家进入“好状态”所需的金币数量。
编写一个程序来找出所需的最少金币数量。
入力
输入将以以下形式通过标准输入给出。
N M c_1 c_2 : c_N a_1 b_1 r_1 a_2 b_2 r_2 : a_M b_M r_M
- 1 行中,2 整数 编写一个程序来查找 N (2 ≦ N ≦ 100,000) 和 将其放在 M (1 ≦ M ≦ 200,000) 用空格分隔。这意味着这座城市 N 这条路是 M 代表有一本书。
- 2 在 N 行包含一个表示有关城市的信息的整数。 给出了 c_i (1 ≦ c_i ≦ 1,000,000,000) 。这是一座城市 表示需要 i 设立交易站需要金币。 需要 c_i 件。
- N+2 在 M 线表示有关道路的信息。 3 整数 编写一个程序来查找 a_i, b_i (1 ≦ a_i < b_i ≦ N), r_i (1 ≦ r_i ≦ 1,000,000,000) 用空格分隔。这就是路 i 是一座城市 a_i 和城市 b_i 在终点,需要铺设 r_i 表示需要。
部分点
针对此问题设置了部分分数。
- N ≦ 8 和 满足 M ≦ 10 的数据集 如果您正确回答 1 , 如果您对10 分被给予。
- N ≦ 12 和 满足 M ≦ 66 的数据集 如果您正确回答 2 的回答正确,除上述之外, 20 分被给予。
- N ≦ 3,000 和 满足 M ≦ 6,000 的数据集 如果您正确回答 3 的回答正确,除上述之外, 30 分被给予。
- 没有附加约束的数据集 4 的回答正确,除上述之外, 40 分被给予。
出力
定义使一个国家进入“良好状态”的最低可能总成本。 在 1 行输出。还在输出末尾添加换行符。
入力例1
7 8 40 50 30 70 70 80 80 1 2 40 1 3 50 1 4 60 2 5 90 3 4 80 4 5 110 5 6 60 6 7 50
出力例1
350
城市及道路布局如下图。
在以下条件下建立交易站并铺设道路。 在
- 都市 1 设立一个交易站。设立交易站需要金币。 连接 40 页。
- 都市 3 设立一个交易站。设立交易站需要金币。 连接 30 页。
- 都市 5 设立一个交易站。设立交易站需要金币。 连接 70 页。
- 道 1 (都市 1 和城市 2 )。人行道上的金币 40 页。
- 道 3 (都市 1 和城市 4 )。人行道上的金币 60 页。
- 道 7 (都市 5 和城市 6 )。人行道上的金币 60 页。
- 道 8 (都市 6 和城市 7 )。人行道上的金币 50 页。
城市和道路的最终状态如下所示。在这里,有贸易站的城市显示为双边界,铺好的道路显示为双线。
在这种情况下,国家可以说处于“良好状态”。事实上, 交易站位于
- 都市 1 。
- 都市 2 中没有贸易站,但有一条柏油路。 通过 1 拥有贸易站的城市 您可以移至 1 。 一条铺有
- 都市 3 。
- 都市 4 中没有贸易站,但有一条柏油路。 通过 3 拥有贸易站的城市 您可以移至 1 。 一条铺有
- 都市 5 。
- 都市 6 中没有贸易站,但有一条柏油路。 通过 7 拥有贸易站的城市 您可以移至 5 。 一条铺有
- 都市 7 中没有贸易站,但有一条柏油路。 通过 7 的路 8 拥有贸易站的城市 您可以移至 5 。 一条铺有
。金币 需要 40 + 30 + 70 + 40 + 60 + 60 + 50 = 350 页。
入力例2
3 3 50 50 50 1 2 60 1 3 60 2 3 60
出力例2
150
在每个城市都有一个交易站会更便宜。
入力例3
5 7 80 70 60 50 40 1 3 20 1 4 70 1 5 30 2 3 30 2 4 90 3 4 40 4 5 80
出力例3
160