https://www.luogu.com.cn/problem/P2865

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;
typedef pair<int, int> pii;
#define m_p make_pair
#define INF 2147483647
#define INFL 9223372036854775807LL

struct edge {
	int v, w;
};

vector<edge> g[5010];
set<pii> h;
int d1[5010], d2[5010];

int main() {
	int n, r;
	cin >> n >> r;
	for (int i = 1; i <= n; i++) d1[i] = d2[i] = INF;
	while (r--) {
		int a, b, d;
		cin >> a >> b >> d;
		g[a].push_back((edge) {b, d});
	}
	h.insert(pii(0, 1));
	d1[1] = 0; 
	while (!h.empty()) {
		int d = h.begin() -> first;
		int u = h.begin() -> second;
		h.erase(h.begin());
		for (int i = 0; i < g[u].size(); i++) {
			int v = g[u][i].v;
			int w = g[u][i].w;
			if (d1[v] > d + w) {
				h.erase(pii(d1[v], v));
				d2[v] = d1[v];
				d1[v] = d + w;
				h.insert(pii(d1[v], v)); 
			} else if (d2[v] > d + w) {
				h.erase(pii(d2[v], v));
				d2[v] = d + w;
				h.insert(pii(d2[v], v));
			}
		}
	}
	cout << d2[n];
	return 0;
}