90pts WA on #4

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

const int maxn = 5005, INF = 0x3f3f3f3f;
LL n, m, x, y, z;
struct node
{
	LL u, w;
	friend bool operator < (const node &a, const node &b)
	{
		return a.w > b.w;
	}
};
vector <node> e[maxn];
priority_queue <node> q;
LL dis[3][maxn];
void Dij()
{
	memset(dis, INF, sizeof dis);
	dis[0][1] = 0;
	q.push((node) {1, 0});
	while(!q.empty())
	{
		int u = q.top().u, d = q.top().w;
		q.pop();
		if(d > dis[1][u]) continue;
		for(node i : e[u])
		{
			int v = i.u, w = i.w;
			if(dis[0][v] > d + w)
			{
				dis[1][v] += dis[0][v];
				dis[0][v] = d + w;
				q.push((node) {v, dis[0][v]});
			}
			if(dis[1][v] > d + w and dis[0][v] < d + w)
			{
				dis[1][v] = d + w;
				q.push((node) {v, dis[1][v]});
			}
		}
	}
}

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		cin >> x >> y >> z;
		e[x].push_back((node) {y, z});
		e[y].push_back((node) {x, z});
	}
	Dij();
	cout << dis[1][n];
	return 0;
}