超頂点 \(W _ S,W _ T\) を作り、頂点 \(i\) から \(W _ S\) へ \(X _ i\) 分で、\(W _ S\) から \(W _ T\) へ \(Y\) 分で、\(W _ T\) から頂点 \(j\) へ \(X _ j\) 分で移動できるようにすることで、頂点数 \(N+2\) 、辺数 \(2N+M+1\) のグラフの単一始点最短経路問題に帰着されます。

これは、Dijkstra 法などを用いることで解くことができます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <queue>
#include <ranges>

int main() {
    using namespace std;
    unsigned N, M, Y;
    cin >> N >> M >> Y;

    vector<vector<pair<unsigned, unsigned>>> edges(N + 2);
    for (unsigned i{}; i < M; ++i) {
        unsigned u, v, T;
        cin >> u >> v >> T;
        edges[--u].emplace_back(--v, T);
        edges[v].emplace_back(u, T);
    }

    for (unsigned i{}; i < N; ++i) {
        unsigned X;
        cin >> X;
        edges[i].emplace_back(N, X); // 各頂点から W_S へ
        edges[N + 1].emplace_back(i, X); // W_T から各頂点へ
    }
    
    edges[N].emplace_back(N + 1, Y); // W_S から W_T へ

    // Dijkstra 法で最短経路を求める
    vector<unsigned> distance(N + 2, 3000000000);
    priority_queue<pair<unsigned, unsigned>, vector<pair<unsigned, unsigned>>, greater<>> pq;
    pq.emplace(distance[0] = 0, 0);
    while (!empty(pq)) {
        const auto [dist, now]{pq.top()};
        pq.pop();
        if (distance[now] < dist) continue;

        for (const auto& [next, cost] : edges[now])
            if (distance[next] > dist + cost)
                pq.emplace(distance[next] = dist + cost, next);
    }

    for (const auto d : distance | views::take(N) | views::drop(1))
        cout << d << " ";
    cout << endl;
    return 0;
}