Track multiple values during Dijkstra:
dist = array, all infinity
cnt = array, all 0
minE = array, all infinity
maxE = array, all 0
dist[1] = 0
cnt[1] = 1
minE[1] = 0
maxE[1] = 0
while pq is not empty:
(d, u) = pq.pop()
if d > dist[u]:
continue
for (v, w) in adj[u]:
newD = dist[u] + w
if newD < dist[v]:
dist[v] = newD
cnt[v] = cnt[u]
minE[v] = minE[u] + 1
maxE[v] = maxE[u] + 1
pq.push((newD, v))
else if newD == dist[v]:
cnt[v] = (cnt[v] + cnt[u]) mod MOD
minE[v] = min(minE[v], minE[u] + 1)
maxE[v] = max(maxE[v], maxE[u] + 1)