AT_abc463_e [ABC463E] Roads and Gates

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.

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 the answers to the problems for $ k=2,3,\ldots,N $ in this order, separated by spaces.

### Sample Explanation 1 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 Explanation 2 Note that the answer may be $ 2 ^ {31} $ or greater. ### 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.