被Dij搞崩Day3，求调，目前超时

/*
work by:Tothetime_tolife
time:1s
space:128MB
*/
#include<bits/stdc++.h>
#define int long long
#define Tothetime_tolife using
#define AK namespace
#define IOI std
Tothetime_tolife AK IOI;
const int Mod1=998244353;
const int Mod2=1000000007;
int gcd(int a,int b){return __gcd(a,b);}
int lcm(int a,int b){return a*b/gcd(a,b);}
int qpow(int a,int b){int res=1;while(b){if(b&1){res=res*a%Mod1;}b>>=1;a=a*a%Mod1;}return res%Mod1;}
template <typename T> inline void read(T& x) {
    x=0;T f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=x*f;
    return;
}
template <typename T,typename ...Arg>void read(T& x,Arg& ...arg){
    read(x);
    read(arg...);
}
template <typename T>void write(T x) {
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
template <typename T,typename ...Arg>void write(T& x,Arg& ...arg){
    write(x);
    putchar(' ');
    write(arg...);
}
const int N=2505;
const int M=6205;
const int Max=2147483647;
int n,m,l,S,T,b,ans,dis[N],f[N],head[N],cnt,x,y,z,t,Cnt=1;
int to[2*M],nxt[2*M],val[2*M],X[2*M],Y[2*M],Z[2*M];
bool vis[N];
struct Node{
    int id,w;
    friend bool operator<(const Node A,const Node B){
        return A.w>B.w;
    }
};
inline void add(int u,int v,int w){
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
    val[cnt]=w;
    return;
}
priority_queue<Node> Q;
int dij(int sx){
    for(int i=1;i<=n;i++) dis[i]=Max;
    Node now;
    now.id=S;now.w=0;
    dis[S]=0;
    int p,ww;
    Q.push(now);
    memset(vis,0,sizeof(vis));
    while(!Q.empty()){
        Node x=Q.top();
        Q.pop();
        p=x.id;
        ww=x.w;
        if(vis[p] || dis[p]!=ww){
            continue;
        }
        vis[p]=1;
        int u;
        for(register int i=head[p];f[to[i]]<=sx;i=nxt[i]){
            u=to[i];
            if(dis[p]+val[i]<dis[u]){
                dis[u]=dis[p]+val[i];
                now.id=u;now.w=dis[u];
                Q.push(now);
            }
        }
    }
    if(dis[n]<b){
        return 1;
    }
    return 0;
}
signed main()
{
    //;;;;;
    read(n,m,b);
    S=1;
    for(int i=1;i<=n;i++){
        read(f[i]);
    }
    for(int i=1;i<=m;i++){
        read(x,y,z);
        add(x,y,z);
        add(y,x,z);
    }
    int l=0,r=100000005,mid;
    while(l<=r){
        mid=(l+r)>>1;
        //cout<<l<<" "<<r<<endl;
        if(dij(mid)){
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    cout<<l;
    return 0;
}
//QwQ

又被最短路搞崩了QwQ，求调。希望别再被抓住。