这是一道次短路的题

但是本题有两个坑

1. 注意边权的范围，一定要在所有与距离有关的地方开 long long
2. 本题所求的并不是次短路，而是与最短路不同的最短的路径，如果最短路不止一条，那么就输出最短路的长度

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

const int MAXN=400005;

long long init(){

	long long rv=0,fh=1;

	char c=getchar();

	while(c<'0'||c>'9'){

		if(c=='-') fh=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9'){

		rv=(rv<<1)+(rv<<3)+c-'0';

		c=getchar();

	}

	return rv*fh;

}

long long n,m,T,dis[MAXN],dis2[MAXN],head[MAXN],nume;

struct edge{

	long long to,nxt,dis;

}e[MAXN];

void adde(int from,int to,int dis){

	e[++nume].to=to;

	e[nume].dis=dis;

	e[nume].nxt=head[from];

	head[from]=nume;

}

struct cmp{

	bool operator()(const int &a,const int &b)const{

		return dis[a]>dis[b];

	}

};

void sec_dij(){

	memset(dis,0x3f,sizeof(dis));

	int cnt[MAXN];

	memset(dis2,0x3f,sizeof(dis2));

	memset(cnt,0,sizeof(cnt));

	dis[1]=0;

	priority_queue <int,vector<int>,cmp> q;

	q.push(1);

	while(!q.empty()){

		int u=q.top();q.pop();

		for(int i=head[u];i;i=e[i].nxt){

			int v=e[i].to;

			if(dis[v]>dis[u]+e[i].dis){

				long long t=dis[v];

				dis[v]=dis[u]+e[i].dis;

				if(dis2[v]>t) dis2[v]=t;

				q.push(v);

			}else if(dis[v]<dis[u]+e[i].dis){

				if(dis[u]+e[i].dis<dis2[v]){

					dis2[v]=dis[u]+e[i].dis;

					q.push(v);

				}

			}

			if(dis2[v]>dis2[u]+e[i].dis){

				dis2[v]=dis2[u]+e[i].dis;

				q.push(v);

			}

		}

	}

	queue <int> qq;

	qq.push(n);

	bool f[MAXN];

	memset(f,0,sizeof(f));

	f[n]=1;

	while(!qq.empty()){

		int u=qq.front();qq.pop();

		for(int i=head[u];i;i=e[i].nxt){

			int v=e[i].to;

			if(dis[u]==dis[v]+e[i].dis){

				cnt[u]++;

				if(!f[v]) qq.push(v);

				f[v]=1;

			}

		}

	}

	bool flag = 0;

	for(int i = 1; i <= n; i++) if(cnt[i] >= 2) {flag = 1;break;}

	if(flag) cout<<dis[n]<<endl;

	else cout<<dis2[n]<<endl;

}

int main(){

	T=init();

	while(T--){

		memset(e,0,sizeof(e));

		memset(head,0,sizeof(head));

		nume=0;

		n=init();m=init();

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

			int u=init(),v=init(),di=init();

			adde(u,v,di);

			adde(v,u,di);

		}

		sec_dij();

	}

	return 0;

}