【模板】次短路算法

#include<bits/stdc++.h>
using namespace std;
template<class T>inline void qread(T& x){
    char c;bool f=false;x=0;
    while((c=getchar())<‘0‘||‘9‘<c)if(c==‘-‘)f=true;
    for(x=(c^48);‘0‘<=(c=getchar())&&c<=‘9‘;x=(x<<1)+(x<<3)+(c^48));
    if(f)x=-x; 
}
template<class T,class... Args>inline void qread(T& x,Args&... args){qread(x),qread(args...);}
inline int rqread(){
    char c;bool f=false;int x=0;
    while((c=getchar())<‘0‘||‘9‘<c)if(c==‘-‘)f=true;
    for(x=(c^48);‘0‘<=(c=getchar())&&c<=‘9‘;x=(x<<1)+(x<<3)+(c^48));
    return f?-x:x;
}
template<class T>inline T Max(const T x,const T y){return x>y?x:y;}
template<class T>inline T Min(const T x,const T y){return x<y?x:y;}
template<class T>inline T fab(const T x){return x>0?x:-x;}
#define INF 0x3f3f3f3f
const int MAXM=100000;
const int MAXN=5000;
struct edge{
    int to,nxt,w;
    edge(){}
    edge(const int T,const int N,const int W):to(T),nxt(N),w(W){}
}e[(MAXM<<1)+5];
int tail[MAXN+5],N,M,ind;
void add_edge(const int u,const int v,const int w){
    e[++ind]=edge(v,tail[u],w);tail[u]=ind;
    e[++ind]=edge(u,tail[v],w);tail[v]=ind;
}
int disx[MAXN+5],disy[MAXN+5];
struct node{
    int u,w;
    node(){}
    node(const int U,const int W):u(U),w(W){}
    bool operator<(const node a)const{return !(w<a.w);}
};
void dijkstra(const int s){
    for(int i=1;i<=N;++i)disx[i]=disy[i]=INF;
    priority_queue<node>Q;
    Q.push(node(s,(disx[s]=0)));
    while(!Q.empty()){
        int now=Q.top().u,dis=Q.top().w;Q.pop();
        if(dis>disy[now])continue;
        for(int i=tail[now],calc,v;i;i=e[i].nxt){
            v=e[i].to,calc=dis+e[i].w;
            if(calc<disx[v]){
                swap(calc,disx[v]);
                Q.push(node(v,disx[v]));
            }
            if(disx[v]<calc&&calc<disy[v]){
                disy[v]=calc;
                Q.push(node(v,disy[v]));
            }
        }
    }
}
signed main(){
    qread(N,M);
    for(int i=1,a,b,c;i<=M;++i){
        qread(a,b,c);
        add_edge(a,b,c);
    }
    dijkstra(1);
    // for(int i=1;i<=N;++i)printf("%d %d\n",disx[i],disy[i]);
    printf("%d\n",disy[N]);
    return 0;
}