Problem

You are given a undirected graph with n nodes (numbered from 1 to n) and m edges. Alice and Bob are now trying to play a game.
Both of them will take different route from 1 to n (not necessary simple).
Alice always moves first and she is so clever that take one of the shortest path from 1 to n.
Now is the Bob's turn. Help Bob to take possible shortest route from 1 to n.
There's neither multiple edges nor self-loops.
Two paths S and T are considered different if and only if there is an integer i, so that the i-th edge of S is not the same as the i-th edge of T or one of them doesn't exist.

Input

The first line of input contains an integer T(1 <= T <= 15), the number of test cases.
The first line of each test case contains 2 integers n, m (2 <= n, m <= 100000), number of nodes and number of edges. Each of the next m lines contains 3 integers a, b, w (1 <= a, b <= n, 1 <= w <= 1000000000), this means that there's an edge between node a and node b and its length is w.
It is guaranteed that there is at least one path from 1 to n.
Sum of n over all test cases is less than 250000 and sum of m over all test cases is less than 350000.

Output

For each test case print length of valid shortest path in one line.

Sample Input

2
3 3
1 2 1
2 3 4
1 3 3
2 1
1 2 1

Sample Output

5
3

Hint

For testcase 1, Alice take path 1 - 3 and its length is 3, and then Bob will take path 1 - 2 - 3 and its length is 5.
For testcase 2, Bob will take route 1 - 2 - 1 - 2 and its length is 3

思路

典型的次短路问题，还是Dijkstra。定义dis[]和dis2[]数组分别记录最短路和次短路，一同更新就好。另外再次敲脑袋提醒自己每个case前面记得把邻接表清空。。。

代码

#include<cstdio>  
#include<cstring>  
#include<algorithm>  
#include<queue>
using namespace std;  
const long long N = 100000 + 5;    
long long dis[N];  
long long dis2[N];  
long long vis[N];  
vector<long long>g[N],e[N];  
long long n, m; 
struct point{  
  long long num;  
  long long dis;  
  bool operator<(const point &b)const{  
      return dis>b.dis;  
  }  
  point(long long d,long long n):num(n),dis(d){} 
};
void add(long long v,long long u,long long c){  
  g[v].push_back(u);  
  e[v].push_back(c);  
}  
void dijkstra(long long s){  
  memset(dis,0x3f,sizeof(dis));  
  memset(dis2,0x3f,sizeof(dis2));  
  priority_queue<point>q;    
  dis[s]=0;  
  q.push(point(0,1));  
  while (!q.empty()){  
    point p = q.top(); 
        q.pop();  
    long long v=p.num;  
    long long d=p.dis;  
    if(dis2[v]<d)continue;  
    for(long long i=0;i<g[v].size();i++){  
      long long c=e[v][i];  
      long long u=g[v][i];  
      long long d2=d+c;  
      if(dis[u]>d2){  
          swap(dis[u],d2);  
          q.push(point(dis[u],u));  
      }  
      if(dis2[u]>d2&&dis[u]<d2){  
          dis2[u]=d2;  
          q.push(point(dis2[u],u));  
      }     
    }  
  }  
}  
int main(){ 
  int t;
  scanf("%d",&t);
  while(t--){
    for(int i=0;i<N;i++){g[i].clear();e[i].clear();}
    scanf("%lld%lld",&n,&m);
    long long a,b,w;  
    for(long long i=0;i<m;i++){  
      scanf("%lld%lld%lld",&a,&b,&w);  
      add(a,b,w);  
      add(b,a,w);  
    }  
    dijkstra(1);  
    printf("%lld\n", dis2[n]);  
  }
  return 0; 
}