估计是 Hack 数据，找了快 $2$ 个月了，有没有大佬救救我……

#include<bits/stdc++.h>
using namespace std;

int n, m, b, f[10010];
long long d[10010];
bool vis[10010];
struct Edge
{
    int v, w;
    Edge(int v, int w) : v(v), w(w) {}
};
struct Node
{
    int u;
    long long d;
    Node(int u, long long d) : u(u), d(d) {}
    bool operator < (const Node &a) const
    { return d > a.d; }
};
vector<Edge> adj[10010];

void dijkstra(int mid)
{
    memset(d, 0x3f, sizeof(d));
    memset(vis, false, sizeof(vis));
    d[1] = 0;
    priority_queue<Node> q;
    q.push((Node){1, 0});
    while (!q.empty())
    {
        int u = q.top().u;
        q.pop();
        if (u == n) return;
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = 0; i < adj[u].size(); i++)
        {
            int v = adj[u][i].v, w = adj[u][i].w;
            if (f[v] > mid) continue;
            if (d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                q.push((Node){v, d[v]});
            }
        }
    }
}

void dijkstra_lt()
{
    memset(d, 0x3f, sizeof(d));
    memset(vis, false, sizeof(vis));
    d[1] = 0;
    priority_queue<Node> q;
    q.push((Node){1, 0});
    while (!q.empty())
    {
        int u = q.top().u;
        q.pop();
        if (u == n) return;
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = 0; i < adj[u].size(); i++)
        {
            int v = adj[u][i].v, w = adj[u][i].w;
            if (d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                q.push((Node){v, d[v]});
            }
        }
    }
}

int main()
{
    cin >> n >> m >> b;
    for (int i = 1; i <= n; i++) cin >> f[i];
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back((Edge){v, w});
        adj[v].push_back((Edge){u, w});
    }
    dijkstra_lt();
    if (d[n] > b) cout << "AFK" << endl;
    else
    {
        int l = min(f[1], f[n]), r = 0, ans;
        for (int i = 1; i <= n; i++) r = max(r, f[i]);
        while (l <= r)
        {
            int mid = (l + r) / 2;
            dijkstra(mid);
            if (d[n] <= b) ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        cout << ans << endl;
    }
    return 0;
}