求调

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rl register ll

const ll N = 5010, M = 2e5 + 10;

ll n, m;

ll tot, ne[M], e[M], w[M], h[N], dis[N][2];

bool st[N][2];

struct node
{
	ll id, dis, type;
	bool operator <(const node &x) const 
	{
		return dis > x.dis;
	}
};

priority_queue<node> q;

inline void add(ll a, ll b, ll c)
{
	ne[++tot] = h[a], h[a] = tot, e[tot] = b, w[tot] = c;
}

inline void dij(ll s)
{
	memset(st, 0, sizeof st);
	memset(dis, 0x3f, sizeof dis);
	
	dis[s][0] = dis[s][1] = 0;
	
	q.push({1, 0, 0});
	
	while(q.size())
	{
		node asd = q.top();
		q.pop();
		ll u = asd.id, type = asd.type, dist = asd.dis;
		if(st[u][type]) continue;
		st[u][type] = 1;
		for(rl i=h[u]; ~i; i = ne[i])
		{
			ll v = e[i];
			if(dis[v][0] > dist + w[i])
			{
				dis[v][1] = dis[v][0];
				q.push({v, dis[v][1], 1});
				dis[v][0] = dist + w[i];
				q.push({v, dis[v][0], 0});
			}
			else if(dis[v][1] > dist + w[i])
			{
				dis[v][1] = dist + w[i];
				q.push({v, dis[v][1], 1});
			}
		}
	}
}

int main()
{
	cin >> n >> m;
	
	memset(h, -1, sizeof h);
	
	for(rl i=1; i <= m; ++ i)
	{
		ll a, b, c;
		cin >> a >> b >> c;
		add(a, b, c), add(b, a, c);
	}
	
	dij(1);
	
	cout << dis[n][1] << endl;
	return 0;
}