A city has n junctions 0 .. n-1 and undirected streets streets[i] = [u, v, t] taking t minutes
(t >= 1). Two routes from junction 0 to junction n-1 are different if they use a different
sequence of streets (so two parallel streets give two different routes).
Return the number of routes that take the minimum possible time, modulo 10**9 + 7. Return 0 if
junction n-1 is unreachable; a single junction has exactly one (empty) route.
Examples
Input: n = 4, streets = [[0,1,1],[0,2,1],[1,3,1],[2,3,1]]
Output: 2
Explanation: 0-1-3 and 0-2-3 both take 2 minutes.
Input: n = 4, streets = [[0,1,2],[0,2,1],[2,1,1],[1,3,1],[0,3,4]]
Output: 2
Explanation: the fastest time is 3: 0-1-3 and 0-2-1-3. The direct street takes 4.
Input: n = 1, streets = []
Output: 1
Constraints
1 <= n <= 5000,0 <= len(streets) <= 10**4,1 <= t <= 10**6- Target
O(E log V)time.
Goals
- Extend Dijkstra with a second array that counts ways
- Distinguish 'strictly better' from 'equally good' relaxations
- Keep counts small with a modulus