在处理答案时用了三分（非常奇怪，因为是我自创的），写证明时发现不太对，希望大佬帮忙卡掉它。谢谢大家！！

#include <bits/stdc++.h>
using namespace std;
const int N=3e3+10;
const int INF=0x3f3f3f3f; 
int n,m,nm,k,nxt[N<<1],hd[N],go[N<<1],tot,vis[N];
#define ll long long
ll jz[N<<1],w[N],dis[N];
void add(int x,int y,ll z)
{
	nxt[++tot]=hd[x];go[tot]=y;jz[tot]=z;hd[x]=tot;
	nxt[++tot]=hd[y];go[tot]=x;jz[tot]=z;hd[y]=tot;
	return ;
}
struct node
{
    int u;
	ll zhi;
    bool operator >(const node& x)const{
    	return x.zhi<zhi;
	} 
};
priority_queue< node ,vector <node> , greater <node> > q;

inline ll cheak(ll x)
{
	for(int i=1;i<=n;i++)dis[i]=1e18,vis[i]=0;
    q.push(node{1,0});
    dis[1]=0;
    while(!q.empty())
    {
        int u=q.top().u;q.pop();
    	if(vis[u])continue;
        vis[u]=1;
        for(int i=hd[u];i;i=nxt[i])
		{
			int v=go[i];
			ll zhi=max(jz[i]-x,0ll);
            if(dis[v]>dis[u]+zhi)
            {
                dis[v]=dis[u]+zhi;
                q.push((node){v,dis[v]});
            }	
		}
    }
    return dis[n]+1ll*x*k;
}
int main()
{
	freopen("0.out","r",stdin);
//	freopen("1.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v>>w[i];
        add(u,v,w[i]);
    }
    w[m+1]=w[0]=1e9+7;
    sort(w+1,w+m+1);
    nm=unique(w+1,w+m+1)-w-1;
    int l=1,r=nm;ll ans=cheak(0);
    while(l<=r)
    {
        int mid=(l+r)>>1;
        ll z1=cheak(w[mid-1]),z2=cheak(w[mid]),z3=cheak(w[mid+1]);
        if(z1>=z2&&z2<=z3)
        {
            cout<<min(z2,ans)<<'\n';//long long;
            break;
        }
        if(z1<=z2&&z2<=z3)r=mid-1;
        if(z1>=z2&&z2>=z3)l=mid+1;
    }
//	for(int i=1;i<=nm;i++)
//	{
//		cout<<cheak(w[i])<<' ';
//		ans=min(ans,cheak(w[i]));
//	}
//  cout<<ans<<'\n';	
    return 0;
}
/*
5 7 2
1 5 5
1 2 2
2 3 2
3 4 2
4 5 2
1 4 3
1 3 1
*/