50分求条 杨立国了

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

const int N = 5005;
int n, r, dis[N], dis2[N], cnt[N];
bool f[N];
struct node{
	int v, w;
};
vector<node> a[N];
void spfa()
{
	for (int i = 1; i <= n; i++)
	{
		dis[i] = INT_MAX;
		dis2[i] = INT_MAX;
	}
	dis[1] = 0, dis2[1] = 0;
	queue<int> q;
	q.push(1);
	f[1] = 1;
	cnt[1] = 1;
	while (q.size())
	{
		int k = q.front();
		q.pop();
		f[k] = 0;
		for (int i = 0; i < a[k].size(); i++)
		{
			int v = a[k][i].v, w = a[k][i].w;
			if (dis[k] + w < dis[v])
			{
				dis2[v] = dis[v];
				dis[v] = dis[k] + w;
			}
			else if (dis[k] + w < dis2[v])
			{
				dis2[v] = dis[k] + w;
			}
		}
	}
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> r;
	for (int i = 1; i <= r; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		a[u].push_back({v, w});
		a[v].push_back({u, w});
	}
	spfa();
	cout << dis2[n];
	return 0;
}
/*

*/