E - Roads and Gates Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 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 分かけて移動することができます。

これ以外の方法で AtCoder 国の都市の間を移動することはできません。

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 へは次のようにして 7 分で移動することができます。

  • 1 本目の道路を使い、1 分かけて都市 1 から都市 2 へ移動する。
  • ワープゲートを使い、1+2+3=6 分かけて都市 2 から都市 7 へ移動する。

都市 1 から都市 7 へ 6 分以下で移動することはできないため、k=7 に対する問題の答えは 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

Score : 450 points

Problem Statement

The country of AtCoder has N cities and M roads. The i-th road (1\le i\le M) connects cities u _ i and v _ i bidirectionally, and allows travel from one to the other in T _ i minutes.

Additionally, each city has a warp gate installed, and you can travel from city i\ (1\le i\le N) to city j\ (1\le j\le N) using the warp gate in X _ i+X _ j+Y minutes.

There are no other ways to travel between cities in the country.

For each k=2,3,\ldots,N, solve the following problem:

  • Find the minimum time required to travel from city 1 to city k.

The time required to transfer from a road or warp gate to another road or warp gate at the same city is negligible.

Constraints

  • 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
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Output the answers to the problems for k=2,3,\ldots,N in this order, separated by spaces.

Sample Input 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

Sample Output 1

1 5 6 8 14 7

For example, you can travel from city 1 to city 7 in 7 minutes as follows:

  • Use the first road to travel from city 1 to city 2 in 1 minute.
  • Use the warp gate to travel from city 2 to city 7 in 1+2+3=6 minutes.

It is impossible to travel from city 1 to city 7 in 6 minutes or less, so the answer for k=7 is 7.

Sample Input 2

2 0 1000000000
1000000000 1000000000

Sample Output 2

3000000000

Note that the answer may be 2 ^ {31} or greater.

Sample Input 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

Sample Output 3

2432 999 1672 2037 1762 1753 967 1723 1677 953 733