由于答案具有单调性，即付钱少的方案一定被包含在付钱多的方案内，那么我们可以二分答案，把问题转化为：是否存在一种合法的升级方法，使花费不超过mid，然后找就行。

在做最短路的时候需要把边权大于mid的边边权变为1，不超过mid的边权为0，然后判断看1到n最短路是否超过K。0到1e6一直二分求出答案，应该不会TLE。

#include<bits/stdc++.h>
using namespace std;
int head[100020],ver[1000020],edge[1000020],nxt[1000020],d[100020];
bool v[100020];
int n,m,k,tot,mid;
priority_queue< pair<int,int> > q; //优先队列 
void add(int x,int y,int z){ //加边 
    ver[++tot]=y;
	edge[tot]=z;
	nxt[tot]=head[x];
	head[x]=tot;
}
void dijkstra(){ //模板部分是照书抄的（ 
    memset(d,0x3f,sizeof(d)); //因为是取min所以d[n]要开大点 
    memset(v,0,sizeof(v)); //初始化每个节点都没被访问过 
    d[1]=0; //初始化 
    q.push(make_pair(0,1));
    while(q.size()){ //只要q不为空 
        int x=q.top().second;
        q.pop(); //用完了扔掉 
        if(v[x])continue;
        v[x]=1; //加上访问标记 
        for(int i=head[x];i;i=nxt[i]){ //遍历以当前节点为起点的每一条边 
            int y=ver[i],z=edge[i];
            if(z>mid)z=1; //把边权大于mid的边边权变为1
            else z=0; //不超过mid的边权为0
            if(d[y]>d[x]+z){ //三角形不等式 
                d[y]=d[x]+z; //更新最短路 
                q.push(make_pair(-d[y],y)); //堆优化 
            }
        }
    }
}
int main(){
    scanf("%d %d %d",&n,&m,&k);
    for(int i=1;i<=m;i++){
        int x,y,z; //起点终点边权 
        scanf("%d %d %d",&x,&y,&z);
        add(x,y,z); //因为是双向边所以需要加两次 
        add(y,x,z);
    }
    int l=0,r=1000000; 
    int ans=-1;
    while(l<=r){ //二分答案d[n] 
        mid=l+(r-l)/2;
        dijkstra();
        if(d[n]<=k){
            r=mid-1;
            ans=mid;
        }
        else l=mid+1;
    }
    printf("%d\n",ans); //好耶 
    return 0;
}