Question about Prims algorithm where weights are between 1 and some constant W
The solution is to preprocess the adjacency matrix so that each vertex now has a list of adjacent vertices. When decreasing keys, you address each edge at most twice, so this part of the algorithm runs in $O(E)$.

The basic observation here is that you can implement a priority queue in $O(W)$ if the number of different weights is $W$. You have to be careful to maintain an array mapping the vertices to their current location in the priority queue, but then all operations are indeed $O(W)$.