二分+最短路 WA on Sub0 Sub1#1

#include<bits/stdc++.h>
#define int long long 
#define INF 1e9
using namespace std;
const int N=5e4+5;
int n,m,b;
int f[N],dp[N];
int u,v,w;
bool vis[N];
struct K{
    int x,id;
    bool operator <(const K &k)const{
        return k.x<x;
    }
};
priority_queue<K> q;
struct node{
    int v,w;
};
vector<node> edge[N];
bool check_Dij(int mid)
{
    if(f[1]>mid)
        return 0;
    q.push({1,0});
    while(q.size())
    {
        u=q.top().id;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto i:edge[u])
        {
            v=i.v,w=i.w;
            if(f[v]<=mid&&dp[v]>dp[u]+w)
            {
                dp[v]=dp[u]+w;
                q.push({v,dp[v]});
            }
        }
    }
    if(dp[n]<=b)
        return 1;
    return 0;
}
void init()
{
    memset(vis,0,sizeof vis);
    memset(dp,0x3f,sizeof dp);
    dp[1]=0;
    for(int i=1;i<=n;i++)
        edge[i].clear();
}
int rr;
signed main()
{
    cin>>n>>m>>b;
    for(int i=1;i<=n;i++)
        cin>>f[i],rr=max(rr,f[i]);
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        edge[u].push_back({v,w});
        edge[v].push_back({u,w});
    }
    int l=1,r=rr;
    while(l<r)
    {
        int mid=l+r>>1;
        init();
//      cout<<mid<<'\n';
        if(check_Dij(mid)) r=mid-1;
        else l=mid+1;
    }
    cout<<l<<'\n';
    return 0;
}