我用的是DIJ，每个点经过两次，第二次经过的就是次短路，求分析时间复杂度，我认为仍然是DIJ的时间复杂度，并且AC了。但看了大佬们的题解之后，感觉算法会假掉，求分析。

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	char x=getchar();
	int ans=0,f=1;
	while(x>'9'||x<'0') 
	{
		if(x=='-')
			f=-f;
		x=getchar();
	}
	while(x>='0'&&x<='9') 
	{
		ans=(ans<<3)+(ans<<1)+(x^48);
		x=getchar();
	}
	return ans*f;
}
struct node
{
	int go,cost;
	bool operator < (const node& x) const
	{
		return cost>x.cost;
	}
}; 
vector<node> a[5010];
int f[5010][2];
int book[5010];
void dij()
{
	priority_queue<node> q;
	q.push((node){1,0});
	while(q.size())
	{
		node x=q.top();
		q.pop();
		if(book[x.go]>2)
			continue;
		f[x.go][book[x.go]]=x.cost;
		book[x.go]++;
		for(int i=0;i<a[x.go].size();i++)
			q.push((node){a[x.go][i].go,a[x.go][i].cost+x.cost});
	}
}
int main()
{
	int n=read(),m=read();
	for(int i=1;i<=m;i++)
	{
		int x=read(),y=read(),k=read();
		a[x].push_back((node){y,k});
		a[y].push_back((node){x,k});
	}
	dij();
	cout<<f[n][1];
	return 0;
}