虽然算法难度达不到记笔记的级别但由于个人认为较为重要，故作记录。

抓住最短路和次短路的一个区别，最少一条边不同。

所以不妨正反( \(1\) 和 \(n\) )分别跑最短路。

然后枚举最短路除外的每条边。

此时 \(ans=\min (ans , firstdis[from]+w[edge]+seconddis[to])\) 。

其中 \(firstdis\) 为第一次 dij(1->n) 的 \(dis\) 数组。

\(seconddis\) 为第二次 dij(n->i) 的 \(dis\) 数组。

\(edge\) 表示遍历到的边，\(w[edge]\) 表示边权。

码

//writer:Oier_szc

#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N=5005,M=1e5+5;
int n,m,ans=2e9;
int head[N],ne[M<<1],from[M<<1],to[M<<1],w[M<<1],tot=0;
void add(int u,int v,int W)
{
   to[++tot]=v;
   from[tot]=u;
   w[tot]=W;
   ne[tot]=head[u];
   head[u]=tot;
}
struct node
{
   int id,v;
   bool operator<(const node &W) const
   {
   	return v>W.v;
   };
};
int first_dis[N],second_dis[N];
bool first_vis[N],second_vis[N];
int from_edg[N];
//标记每个点的最短路前驱以便找到最短路 
bool is[M<<1];
//is表示这条边在不在最短路里 
void first_dij()
{
   priority_queue<node> q;
   memset(first_dis,0x3f,sizeof(first_dis));
   first_dis[1]=0;
   q.push(node{1,0});
   while(!q.empty())
   {
   	node now=q.top();
   	q.pop();
   	if(first_vis[now.id]) continue;
   	first_vis[now.id]=true;
   	for(int i=head[now.id];i;i=ne[i])
   	{
   		if(first_dis[now.id]+w[i]<first_dis[to[i]])
   		{
   			from_edg[to[i]]=i;//在第一次跑dijkstra时记录前驱 
   			first_dis[to[i]]=first_dis[now.id]+w[i];
   			q.push(node{to[i],first_dis[to[i]]});
   		}
   	}
   }
}
void second_dij()
{
   priority_queue<node> q;
   memset(second_dis,0x3f,sizeof(second_dis));
   second_dis[n]=0;
   q.push(node{n,0});
   while(!q.empty())
   {
   	node now=q.top();
   	q.pop();
   	if(second_vis[now.id]) continue;
   	second_vis[now.id]=true;
   	for(int i=head[now.id];i;i=ne[i])
   	{
   		if(second_dis[now.id]+w[i]<second_dis[to[i]])
   		{
   			second_dis[to[i]]=second_dis[now.id]+w[i];
   			q.push(node{to[i],second_dis[to[i]]});
   		}
   	}
   }
}
void get_ans()
{
   int now=n;
   while(now)
   {
   	is[from_edg[now]]=true;
   	now=from[from_edg[now]];
   }
   for(int i=1;i<=tot;++i)
   {
   	if(is[i]) continue;
   	ans=min(ans,first_dis[from[i]]+w[i]+second_dis[to[i]]);
   }
}
int main()
{
   scanf("%d%d",&n,&m);
   int r1,r2,r3;
   for(int i=1;i<=m;++i)
   {
   	scanf("%d%d%d",&r1,&r2,&r3);
   	add(r1,r2,r3);
   	add(r2,r1,r3);
   }
   first_dij();
   second_dij();
   get_ans();
   printf("%d\n",ans);
   return 0;
}