[ABC362] D - Shortest Path 3

D - Shortest Path 3

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 425 分

题面

给定一个简单的连通无向图，有 个顶点和 条边。每个顶点 有一个权值 。每条边 双向连接顶点 和 ，并且有一个权值 。

在这个图中，路径的权值定义为路径上出现的顶点和边的权值之和。

对于每个 ，解决以下问题：

• 找出从顶点 到顶点 的最小权值路径。

限制条件

• 若 ，则 。
• 图是连通的。
• 所有输入值为整数。

---

输入

输入从标准输入给出，格式如下：

输出

按顺序在一行中输出 的答案，用空格分隔。

---

输入样例 1

3 3
1 2 3
1 2 1
1 3 6
2 3 2

输出样例 1

4 9

考虑从顶点 到顶点 的路径。路径 的权值为 ，路径 的权值为 。最小权值为 。

考虑从顶点 到顶点 的路径。路径 的权值为 ，路径 的权值为 。最小权值为 。

---

输入样例 2

2 1
0 1
1 2 3

输出样例 2

4

---

输入样例 3

5 8
928448202 994752369 906965437 942744902 907560126
2 5 975090662
1 2 908843627
1 5 969061140
3 4 964249326
2 3 957690728
2 4 942986477
4 5 948404113
1 3 988716403

输出样例 3

2832044198 2824130042 4696218483 2805069468

请注意，答案可能不适合 32 位整数。