Modification of Dijkstra's algorithm
You seem to have chosen a strange metric, in that your wheelchair user apparently prefers travelling 1000km over concrete to even 1cm over gravel.

However, in general, the way to proceed is to combine your two metrics into a single metric in such a way that even the best possible score on the secondary metric can't make the algorithm prefer a path that does worse on the primary metric.

So, I'm going to assume that each edge&nbsp;$e$ has a quality&nbsp;$q_e$ and a length&nbsp;$\ell_e$.  The quality will be a nonnegative integer; the length can be a nonnegative real (or integer&nbsp;&ndash; it doesn't matter). Because Dijkstra likes to minimize, I'll take $q=0$ to be the best possible quality (in the question, you take it to be the worst, but this makes no real difference).

Any path between two vertices can't possibly have length more than $L = \sum_{e\in E} \ell_e$.  This means that, for any path of total length&nbsp;$\ell$, $\ell/(L+1)&lt;1$.  We'll take the weight of the edge&nbsp;$e$ to be $w_e = q_e + \ell_e/(L+1)$, and use these values&nbsp;$w_e$ to run Disjkstra's algorithm. The point is that if a path has total quality&nbsp;$Q$, then it has total weight&nbsp;$W$ with $Q\leq W&lt;Q+1$.  Therefore, the least-weight path is guaranteed to be one of the  best quality paths (smallest $q$-values) and, among those, it's the one of least total length.