1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define sz(x) (int)(x).size()

vector<ll> dijkstra(const vector<vector<pi>>& graph, int s) {
    vector<ll> dist(sz(graph), 1e9);
    set<pair<ll, int>> q;
    q.insert({dist[s] = 1, s});

    while (!q.empty()) {
        auto [d, v] = *q.begin();
        q.erase(q.begin());
        if (d > dist[v])
            continue;
        for (auto [u, w] : graph[v]) {
            if (dist[v] * w < dist[u]) {
                dist[u] = dist[v] * w;
                q.insert({dist[u], u});
            }
        }
    }
    return dist;
}

void heuristic(const vector<vector<pi>>& graph, vector<int>& p) {
    vector<ll> dist = dijkstra(graph, sz(graph) - 1);
    for (int i = 0; i < sz(p); i++)
        p[i] = min(p[i], (int)(p.back() / dist[i]));
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;

        vector<int> p(n);
        for (auto &x : p)
            cin >> x;

        vector<vector<pi>> graph(n);
        vector<vector<pi>> rgraph(n);
        while (m--) {
            int u, v, w;
            cin >> u >> v >> w;
            u--, v--;
            graph[u].push_back({v, w});
            rgraph[v].push_back({u, w});
        }

        heuristic(rgraph, p);

        set<pi> q;
        vector<int> ampli(n, -1);

        q.insert({1, 0});
        while (!q.empty()) {
            auto [d, v] = *(q.begin());
            q.erase(q.begin());
            if (d <= ampli[v])
                continue;
            ampli[v] = d;
            for (auto [u, w] : graph[v]) {
                if (p[u] >= (ll)d * w && d * w > ampli[u])
                    q.insert({d * w, u});
            }
        }
        cout << ampli.back() << '\n';
    }
}