学步园

/*

pair(first,second); 就相当于结构体。
此题的做法是，先找出一条最短路径，把路径记录下来
然后枚举删除最短路的每一条边，再从新计算最短路，
求出值最大的 。。
优化的 dijkstra + 枚举 

*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<utility>
using namespace std;
#define manx 1100
const int inf=99999999;
int g[manx][manx],pre[manx];
int n,m,dist[manx],sum,flag;
typedef pair<int,int>pii;

void init(int n){
    for(int i=0;i<=n;i++){
        g[i][i] = inf;
        for(int j=i+1;j<=n;j++)
            g[i][j] = g[j][i] = inf;
    }    
}

void dijkstra(){
    int tmp_pre[manx], st = 1;
    memset(tmp_pre,-1,sizeof(tmp_pre));
    for(int i=1;i<=n;i++) dist[i] = inf;
    dist[1] = 0;
    priority_queue< pii, vector<pii>, greater<pii> >que; /// pii.first的值从小到大的进行排列 
    que.push(make_pair(dist[st],st));
    while(!que.empty()){
        pii x = que.top();
        int u = x.second;
        que.pop();
        if(dist[u]!=x.first) continue; /// 出现这种情况时，dist[u]之前已经有过优化。 
        for(int v=1;v<=n;v++){
            int tmp=dist[u]+g[u][v];
            if(g[u][v]!=inf && dist[v]>tmp){
                dist[v]=tmp;
                tmp_pre[v] = u;
                que.push(make_pair(dist[v],v));
            }    
        }
    }
    if(!flag){
        memcpy(pre,tmp_pre,sizeof(tmp_pre));
        flag = 1;
    }
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
       	scanf("%d%d",&n,&m);
        int a,b,c;
        init(n);
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&a,&b,&c);
            if(g[a][b]>c) 
            	g[a][b]=g[b][a]=c;
        }
        flag = 0;  sum = 0;
        dijkstra();
        int q = n;
        while(pre[q]!=-1){
            int p = pre[q], val=g[p][q];
            g[p][q] = g[q][p] = inf;
            dijkstra();
            if(dist[n] < inf && sum<dist[n]) sum = dist[n];
            g[p][q] = g[q][p] = val;
            q = p;
        }
        if(!sum) printf("-1\n");
        else printf("%d\n",sum);
    }
}