AT_abc463_e [ABC463E] Roads and Gates

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 $ へ移動するのにかかる時間の最小値を求めよ。 ただし、道路やワープゲートから同じ都市の別の道路やワープゲートへ移動するのにかかる時間は無視できるものとします。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ に対する問題の答えを、この順に空白を区切りとして出力せよ。

### Sample Explanation 1 例えば、都市 $ 1 $ から都市 $ 7 $ へは次のようにして $ 7 $ 分で移動することができます。 - $ 1 $ 本目の道路を使い、 $ 1 $ 分かけて都市 $ 1 $ から都市 $ 2 $ へ移動する。 - ワープゲートを使い、 $ 1+2+3=6 $ 分かけて都市 $ 2 $ から都市 $ 7 $ へ移動する。 都市 $ 1 $ から都市 $ 7 $ へ $ 6 $ 分以下で移動することはできないため、 $ k=7 $ に対する問題の答えは $ 7 $ です。 ### Sample Explanation 2 答えが $ 2 ^ {31} $ 以上になる場合があることに注意してください。 ### 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 $ - 入力はすべて整数