Considering the contribution of each edge, the problem can be rephrased as follows:

Takahashi starts a travel with several tickets.

• Whenever he visits vertex \(v\), he consumes \(nW _ v\) units of fuel, if he has \(n\) tickets.
• Whenever he passes though an edge, he releases one ticket.

Minimise the fuel consumed during the travel since visiting vertex \(1\) until reaching vertex \(i\) by appropriately determining the number of his initial tickets and his path.

In an optimal travel, Takahashi never visits the same vertex twice (otherwise, he can omit the travel from his first visit to his last visit to vertex \(v\) to reduce the consumption). Therefore, it is sufficient to initially have up to \((N-1)\) tickets.

Consider a directed graph with vertices \((v,n)\) for all vertices \(v\) and possible numbers of remaining tickets \(n\), with the following weighted directed edges:

• for each edge \((u,v)\) in the original graph and \(1\le n\le N-1\), an edge from \((u,n)\) to \((v,n-1)\) of weight \(nW _ u\).

Then it is enough to find the shortest distance from \((1,n)\ (0\le n\le N-1)\) to \((i,0)\) in this graph.

Since this graph is a DAG (Directed Acyclic Graph), we can process the vertices in an appropriate order to find all the desired values with computational complexity of about \(O(NM)\) time and \(O(N)\) space. If use an algorithm like Dijkstra’s algorithm, the time complexity will become \(O((NM+N ^ 2)\log N)\) or \(O(NM+N ^ 2\log N)\), but it may still be accepted if you use a fast language and implement appropriately.

The following is sample code.

#include <iostream>
#include <vector>
#include <limits>
#include <ranges>

int main() {
    using namespace std;
    unsigned N, M;
    cin >> N >> M;
    vector<unsigned> W(N);
    for (auto&& w : W)
        cin >> w;

    vector<pair<unsigned, unsigned>> edges(M);
    for (auto&& [u, v] : edges) {
        cin >> u >> v;
        --u;
        --v;
    }

    constexpr auto inf{numeric_limits<unsigned long>::max() / 2};
    // Initialize DP table with a sufficiently large value
    vector<unsigned long> dp(N, inf), prev(N, inf);
    dp[0] = 0;

    // Compute in descending order of the number of remaining tickets
    for (const auto i : views::iota(1U, N) | views::reverse) {
        swap(dp, prev);
        dp[0] = 0;
        for (const auto& [u, v] : edges) {
            dp[u] = min(dp[u], prev[v] + static_cast<unsigned long>(W[v]) * i);
            dp[v] = min(dp[v], prev[u] + static_cast<unsigned long>(W[u]) * i);
        }
    }

    for (const auto v : dp)
        cout << v << endl;

    return 0;
}