You can use a pair to store the node along with the value (the first element should be the value so that the priority queue compares with this value). Maintain a boolean array visit [ ]
where you will indicate wheather you have visited or not a certain node (intially all false).
Every time you take the front element of the priority queue check if you have visited this node that is check if visit[pq.front().second] == false
. Check for all its adjacent edges and add the nodes reached from this path. If it is true then you should ignore it, as you have already visited it with less length. You will not add more than E edges so the time complexity remains the same.
You can learn more about this approach in this link http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary2#priority.