大佬们，蒟蒻求调， #13WA

#include <bits/stdc++.h>

#define endl '\n'

const int N = 1e5, INF = 1e9 + 7;
typedef std::pair<int, int> PII;

std::vector<int> h(N, -1), e(N), ne(N), w(N);
std::vector<int> f;
int n, m, b, idx;

void Add(int a, int b, int c)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx++;
}

inline bool Dijkstra(int x)
{
    std::priority_queue<PII, std::vector<PII>, std::greater<PII>> heap;
    heap.push({0, 1});
    std::vector<bool> vis(n + 1, 0);
    std::vector<int> dis(n + 1, INF);
    dis[1] = 0;

    while (heap.size())
    {
        int u = heap.top().second;
        heap.pop();
        if (vis[u])
            continue;
        vis[u] = true;

        for (int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if (f[j] > x)
                continue;
            if (dis[j] > dis[u] + w[i] && dis[u] + w[i] <= b )
            {
                dis[j] = dis[u] + w[i];
                heap.push({dis[j], j});
            }
        }
    }
    return dis[n] <= b;
}

void solve() 
{
    std::cin >> n >> m >> b;
    f.push_back(0);
    for (int i = 1; i <= n; i++)
    {
        int x;
        std::cin >> x;
        f.push_back(x);
    }
    std::vector<int> F = f;
    sort(F.begin() + 1, F.end());
    while (m--)
    {
        int a, b, c;
        std::cin >> a >> b >> c;
        Add(a, b, c);
        Add(b, a, c);
    }

    int l = 1, r = n;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (Dijkstra(F[mid]))
            r = mid;
        else
            l = mid + 1;
    }

    if (l > r ||l == r && !Dijkstra(F[l]))
        std::cout << "AFK" << endl;
    else
        std::cout << F[l] << endl;
}

int main() 
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    solve();

    return 0;
}