C++

#include <cstdio>

#include <algorithm>

#include <vector>

#include <queue>

#include <climits>

using namespace std;

struct Edge{

    int n;

    int dist;

};

struct Q_info{

    int n;

    int dist;

    bool operator < (const Q_info &a) const{

        return dist > a.dist;

    }

};

vector<Edge> vec[1010];

priority_queue<Q_info> pq;

int N,M;

int result[1010],path[1010];

int path_[1010];

int stop_a=-1,stop_b=-1;

int start,max_dc=0;

int serch(){

    for(int i=0;i<1010;i++){

        result[i]=INT_MAX;

    }

    path[1]=-1;

    result[1]=0;

    pq.push({1,result[1]});

 

    while(!pq.empty()){

        Q_info info=pq.top();

        pq.pop();

        if(info.dist!=result[info.n])

            continue;

        if(info.n==N)

            break;

 

        for(auto p:vec[info.n]){

            if((p.n==stop_b && info.n==stop_a)

               || (p.n==stop_a && info.n==stop_b))

               continue;

 

            if(result[p.n]>p.dist+info.dist){

                result[p.n]=p.dist+info.dist;

                path[p.n]=info.n;

                pq.push({p.n,result[p.n]});

            }

        }

    }

    return result[N];

}

int main()

{

    for(int i=0;i<1010;i++){

        result[i]=INT_MAX;

    }

    scanf("%d %d",&N,&M);

    for(int i=0;i<M;i++){

        int a,b,t;

        scanf("%d %d %d",&a,&b,&t);

        vec[a].push_back({b,t});

        vec[b].push_back({a,t});

    }

    start=serch();

    if(start==INT_MAX){

        printf("-1");

        return 0;

    }

    int idx=N;

    int i=0;

    while(idx!=-1){

        path_[i++] = idx;

        idx=path[idx];

    }

    for(int j=1;j<i;j++){

        stop_a=path_[j-1];

        stop_b=path_[j];

        int a=serch();

        if(a==INT_MAX){

            printf("-1");

            return 0;

        }

        max_dc=max(max_dc,a-start);

    }

    printf("%d",max_dc);

    return 0;

}