40分 dij堆优化+二分 为什么超时啊

#include<bits/stdc++.h>
using namespace std;
const int oo=1e9+1;
long long Next[50005],head[10005],vet[50005],tot,bl[50005],cost[10005];
int n,m,b,point[10005];

void add(int x,int y,int z){
    Next[++tot]=head[x];
    vet[tot]=y;
    bl[tot]=z;
    head[x]=tot;
}
long long dist[10005],inq[10005];
bool dij(int top){
    if(cost[1]>top) return false;
    for(int i=2;i<=n;i++){
        dist[i]=oo;
        inq[i]=0;
    } 
    dist[1]=0;
    set<pair<int,int> > q;
    q.insert(make_pair(dist[1],1));
    while(q.size()){
        int min_d=q.begin()->first;
        int v=q.begin()->second;
        q.erase(q.begin());
        inq[v]=1;
        for(int i=head[v];i;i=Next[i]){
            int y=vet[i];
            if(inq[y]) continue;
            if(cost[y]>top) continue;
            if(dist[y]>dist[v]+bl[i]){
                q.erase(make_pair(dist[y],y));
                dist[y]=dist[v]+bl[i];
                q.insert(make_pair(dist[y],y));
            }
        }
    }
    return dist[n]<=b;
}
int  binary(int left,int right){
    int ans=1e9+1;
    while(left<=right){
        int mid=(left+right)/2;
        if(dij(point[mid])){
            ans=point[mid];
            right=mid-1;
        }else{
            left=mid+1;
        }
    }
    return ans; 

}
int main(){
    scanf("%d%d%d",&n,&m,&b);
    for(int i=1;i<=n;i++){
        scanf("%d",&cost[i]);
        point[i]=cost[i];
    }
    sort(point+1,point+n+1);
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        if(x==y) continue;
        add(x,y,z);
        add(y,x,z);
    }
    if(!dij(1e9+1)) printf("AFK");
    else printf("%d",binary(1,n));
    return 0;
}