Compute single-source shortest paths in O(n+m) time?
There are many ways to solve this problem in linear time. I'll write the one I found easiest to understand.

The main idea is to transform the weighted graph into an unweighted one. If the number of nodes and edges of the transformed graph remains linear to $n$ and $m$, then we can run BFS to solve it in $O(n+m)$.

The transformation is as follows: for each edge $(u,v)$ of weight $w$, create $w-1$ nodes to connect $u,v$. For example an edge $(a,b)$ of length $3$, we create two dummy nodes and transform it into

$a-d_1-d_2-b$

It is easy to check that this transformation preserves the shortest path between any pairs of nodes. The number of nodes is now $O(n+cm)=O(n+m)$ and the number of edges is $O(m+cm)=O(m)$. Since BFS is linear to the number of nodes and edges, we have a runtime of $O(n+m+m)=O(n+m)$.