When we use a priority_queue for dijkstra, it reduces the complexity to O(E*logV) but it guarentees us that when we pop a node from the heap, we have found the shortest distance to that node. So, whenever I pop a node from the heap, I set processed[node] = true. Then, when I relax any of its neighbors, I don't check if they are processed because I know that if a node can be relaxed, i.e. we found a distance that is smaller than the prev dist computed for it, then that means the node cannot have been processed.

Just to double check, I put a if statement that prints something if processed[v] is true (which, as I said above, should never happen) inside the portion of the code that relaxes node v. However, this fails in some Codeforces test cases because the if statement prints which I don't understand why. I ran this code on https://codeforces.com/problemset/problem/20/C

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

using ll = long long;

#define pc(x) putchar(x)
#define gc() getchar()

inline void writeInt(int n)
{
	int N = n, rev, count = 0;
	rev = N;
	if (N == 0)
	{
		pc('0');
		pc('\n');
		return;
	}
	while ((rev % 10) == 0)
	{
		count++;
		rev /= 10;
	}
	rev = 0;
	while (N != 0)
	{
		rev = (rev << 3) + (rev << 1) + N % 10;
		N /= 10;
	}
	while (rev != 0)
	{
		pc(rev % 10 + '0');
		rev /= 10;
	}
	while (count--)
		pc('0');
	pc(' ');
}

inline int FAST_IO()
{
	char ch;
	int val = 0;
	ch = gc();
	while (ch == '\n' || ch == ' ')
		ch = gc();
	val = 0;
	while (ch >= '0' && ch <= '9')
	{
		val = (val * 10) + (ch - '0');
		ch = gc();
	}
	return val;
}

int n, m;

void print(const vector<int> &parent, int n)
{
	if (n == -1)
		return;
	print(parent, parent[n]);
	writeInt(n);
}


int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	n = FAST_IO();
	m = FAST_IO();
	vector<vector<pair<int, ll>>> adj(n + 1);
	vector<int> parent(n + 1, -1);
	vector<ll> dist(n + 1, LLONG_MAX);
	vector<bool> processed(n + 1, false);

	while (m--)
	{
		int u = FAST_IO();
		int v = FAST_IO();
		int w = FAST_IO();
		adj[u].emplace_back(v, w);
		adj[v].emplace_back(u, w);
	}

	auto cmp = [&dist](const int &a, const int &b)
	{
		return dist[a] > dist[b];
	};

	priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);

	pq.push(1);
	dist[1] = 0;
	while (!pq.empty())
	{
		int u = pq.top();
		pq.pop();
		
		if (u == n)
			break;
		if (processed[u])
			continue;
		processed[u] = true;


		for (auto &[v, w] : adj[u])
		{
			if (dist[u] + w < dist[v]) // if this is true then processed[v] should be false?
			{
				//v can be relaxed -> processed[v] is false

				if (processed[v]) // THIS CODE SHOULD NEVER RUN BUT IT DOES??
				     cout << "dv = " << dist[v] << "\tdu + w = " << (dist[u] + w) << '\n';

				dist[v] = dist[u] + w;
				parent[v] = u;
				// if (!processed[v])//redundant
				pq.push(v);
			}
		}
	}

	if (dist[n] < LLONG_MAX)
		print(parent, n);
	else
		printf("-1");

	return 0;
}