有没有大佬浇浇，孩子卡一下午了，第八个样例一直过不去

/*
 author : Mzx
*/
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'
#define int long long
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second

typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1e9+7;
const int INF=0x3f3f3f3f;
const int maxn = 1e4+10,maxm = 1e5+10;

int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

int n,m,b;
int f[maxn];
int e[maxm],ne[maxm],idx,h[maxn],w[maxm];
int dist[maxn];
bool st[maxn];

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

bool spfa(int x)
{
    memset(dist,0x3f3f3f,sizeof dist);
    memset(st,0,sizeof st);
    queue<int> q;
    if(x < f[1]) return false;
    q.push(1);
    st[1] = true;
    dist[1] = 0;
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t];i != -1;i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[j] && x >= f[j])
            {
                dist[j] = dist[t] + w[j];
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    if(dist[n] > b) return false;
    else return true;
}

void solve() {
    memset(h,-1,sizeof h);
    cin >> n >> m >> b;
    int maxx = -1;
    for(int i = 1;i <= n;i ++)
    {
        cin >> f[i];
        maxx = max(f[i],maxx);
    }
    while(m--)
    {
        int x,y,z;
        cin >> x >> y >> z;
        add(x,y,z),add(y,x,z);
    }
    if(!spfa(10000000000000008)){
        cout<<"AFK";
        return ;
    }
    int l = 0,r = 10000000006;
    while(l <= r){
        long long mid = (l + r) / 2;
        if(spfa(mid)) r = mid - 1;
        else l = mid + 1;
    }
    cout << l << '\n';
}

signed main()
{
    ios;
    solve();
    return 0;
}