分数: 450 点
问题陈述
AtCoder 的国家有 N 城市和 M 道路。 的 i第路 (1\le i\le M) 连接城市 u _ i 和 v _ i 双向,并允许从一个到另一个 T _ i 分钟。
此外,每个城市都安装了传送门,你可以从城市出发 i\ (1\le i\le N) 前往城市 j\ (1\le j\le N) 使用扭曲门 X _ i+X _ j+Y 分钟。
没有其他方式在该国城市之间旅行。
对于每个 k=2,3,\ldots,N,解决以下问题:
- 求从城市出发所需的最短时间 1 前往城市 k.
从一条道路或传送门转移到同一城市的另一条道路或传送门所需的时间可以忽略不计。
约束
- 2\le N\le2\times10 ^ 5
- 0\le M\le2\times10 ^ 5
- 1\le u _ i\lt v _ i\le N\ (1\le i\le M)
- 1\le T _ i\le10 ^ 9\ (1\le i\le M)
- 1\le X _ i\le10 ^ 9\ (1\le i\le N)
- 1\le Y\le 10 ^ 9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M Y u _ 1 v _ 1 T _ 1 u _ 2 v _ 2 T _ 2 \vdots u _ M v _ M T _ M X _ 1 X _ 2 \ldots X _ N
输出
输出问题的答案 k=2,3,\ldots,N 按此顺序,用空格分隔。
示例输入 1
7 7 3 1 2 1 1 3 6 2 3 4 3 5 8 3 7 4 4 5 2 4 7 9 3 1 4 1 5 9 2
示例输出 1
1 5 6 8 14 7
例如,您可以从城市出发 1 前往城市 7 in 7 分钟如下:
- 使用第一条道路从市区出发 1 前往城市 2 in 1 分钟。
- 使用传送门从城市出发 2 前往城市 7 in 1+2+3=6 分钟。
不可能从城市出发 1 前往城市 7 in 6 分钟或更短,所以答案为 k=7 is 7.
示例输入 2
2 0 1000000000 1000000000 1000000000
示例输出 2
3000000000
请注意,答案可能是 2 ^ {31} 或更大。
示例输入 3
12 20 873 2 7 940 6 9 444 6 11 809 7 8 786 9 10 468 7 10 234 6 10 660 4 12 939 8 10 896 1 11 953 8 10 818 4 8 967 3 9 724 6 7 929 3 4 948 1 3 999 10 11 724 7 10 338 1 8 967 1 12 733 581 978 950 629 583 729 554 712 438 930 774 279
示例输出 3
2432 999 1672 2037 1762 1753 967 1723 1677 953 733