You are in a city that consists of n intersections numbered from 0 to n - 1 with bi-directional roads between some intersections. The inputs are generated such that you can reach any intersection from any other intersection and that there is at most one road between any two intersections.

You are given an integer n and a 2D integer array roads where roads[i] = [ui, vi, timei] means that there is a road between intersections ui and vi that takes timei minutes to travel. You want to know in how many ways you can travel from intersection 0 to intersection n - 1 in the shortest amount of time.

Return the number of ways you can arrive at your destination in the shortest amount of time. Since the answer may be large, return it modulo 109 + 7.

&nbsp;
Example 1:

Input: n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
Output: 4
Explanation: The shortest amount of time it takes to go from intersection 0 to intersection 6 is 7 minutes.
The four ways to get there in 7 minutes are:
- 0 ➝ 6
- 0 ➝ 4 ➝ 6
- 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
- 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6


Example 2:

Input: n = 2, roads = [[1,0,10]]
Output: 1
Explanation: There is only one way to go from intersection 0 to intersection 1, and it takes 10 minutes.


&nbsp;
Constraints:


	1 &lt;= n &lt;= 200
	n - 1 &lt;= roads.length &lt;= n * (n - 1) / 2
	roads[i].length == 3
	0 &lt;= ui, vi &lt;= n - 1
	1 &lt;= timei &lt;= 109
	ui != vi
	There is at most one road connecting any two intersections.
	You can reach any intersection from any other intersection.


class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        graph = defaultdict(dict)
        for u, v, w in roads:
            graph[u][v] = graph[v][u] = w
        dist = {i:float(inf) for i in range(n)}
        ways = {i:0 for i in range(n)}
        dist[0], ways[0] = 0, 1
        heap = [(0, 0)]
        while heap:
            d, u = heapq.heappop(heap)
            if dist[u] < d: 
                continue
            for v in graph[u]:
                if dist[v] == dist[u] + graph[u][v]:
                    ways[v] += ways[u]
                elif dist[v] > dist[u] + graph[u][v]:
                    dist[v] = dist[u] + graph[u][v]
                    ways[v] = ways[u]
                    heapq.heappush(heap, (dist[v], v))
        return ways[n-1] % ((10 ** 9) + 7)
class Solution {
    class Pair{
        int node;
        int dist;
        Pair(int node , int dist){
            this.node = node;
            this.dist = dist;
        }
    }
    public int countPaths(int n, int[][] roads) {
        int mod = (int)Math.pow(10 , 9) + 7;
        ArrayList<ArrayList<Pair>> adj = new ArrayList<>();
        int rows = roads.length;
        for(int i = 0 ; i < n ; i++)
            adj.add(new ArrayList<Pair>());
        for(int i = 0 ; i < rows ; i++){
            int from = roads[i][0];
            int to = roads[i][1];
            int dis = roads[i][2];
            adj.get(from).add(new Pair(to , dis));
            adj.get(to).add(new Pair(from , dis));
        }
        PriorityQueue<Pair> pq = new PriorityQueue<>((aa , bb) -> aa.dist - bb.dist);
        pq.add(new Pair(0 , 0));
        long[] ways = new long[n];
        ways[0] = 1;
        int[] dist = new int[n];
        Arrays.fill(dist , Integer.MAX_VALUE);
        dist[0] = 0;
        while(!pq.isEmpty()){
            Pair p = pq.remove();
            int node = p.node;
            int dis = p.dist;
            for(Pair pa : adj.get(node)){
                if((dis + pa.dist) < dist[pa.node]){
                    ways[pa.node] = ways[node];
                    dist[pa.node] = dis + pa.dist;
                    pq.add(new Pair(pa.node , dist[pa.node]));
                }
                else if((dis + pa.dist) == dist[pa.node]){
                    ways[pa.node] += ways[node];
                    ways[pa.node] = ways[pa.node] % mod;
                }
            }
        }
        return (int)ways[n - 1];
    }
}
class Solution {
public:
    int countPaths(int n, vector<vector<int>>& roads) {
        int mod = 1e9+7;
        vector<vector<pair<int, int>>> graph(n);
        for(auto &road: roads) {
            graph[road[0]].push_back({road[1], road[2]});
            graph[road[1]].push_back({road[0], road[2]});
        }
        
        vector<long long> distance(n, LONG_MAX);
        vector<int> path(n, 0);
        
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
        pq.push({0, 0});
        distance[0] = 0;
        path[0] = 1;
        
        while(!pq.empty()) {
            pair<long long, int> t = pq.top();
            pq.pop();
            
            for(auto &nbr: graph[t.second]) {
                long long vert = nbr.first;
                long long edge = nbr.second;
                
                if(distance[vert] > distance[t.second] + edge) {
                    distance[vert] = distance[t.second] + edge;
                    pq.push({distance[vert], vert});
                    path[vert] = path[t.second] %mod;
                }
                else if(distance[vert] == t.first + edge) {
                    path[vert] += path[t.second];
                    path[vert] %= mod;
                }
            }
        }
        
        return path[n-1];
    }
};
/**
 * @param {number} n
 * @param {number[][]} roads
 * @return {number}
 */
var countPaths = function(n, roads) {
    let adj = {}, dist = Array(n).fill(Infinity), minHeap = new MinHeap(), count = Array(n).fill(1);

    //CREATE ADJ MATRIX
    for(let [from, to , weight] of roads){
        adj[from] = adj[from] || []
        adj[from].push([to, weight]);
        adj[to] = adj[to] || []
        adj[to].push([from, weight]);
    }

    //PUT START IN QUEUE
    dist[n-1] = 0;
    minHeap.enqueue(n-1, 0);

    while(minHeap.getSize()){
        let [node, curDist] = minHeap.dequeue();
        let children = adj[node] || [];
        for(let [childNode, childWeight] of children){

            //IF PATH ALREADY FOUND WITH THIS VALUE THEN ADD COUNT REACHED UNTIL NOW
            if(curDist + childWeight === dist[childNode]){
                count[childNode] = (count[childNode] +count[node]) % 1000000007;
            } //IF NOT PATH FOUND YET THEN ADD COUNT OF WAYS TO THE NODE WE CAME FROM
            else if(curDist + childWeight < dist[childNode]){
                count[childNode] = count[node];
                dist[childNode] = curDist + childWeight;
                minHeap.enqueue(childNode, dist[childNode]);
            }
        }
    }
    return count[0];
};

class MinHeap{
    constructor(list = []){
        this.tree = [null];
        this.list = list;
        this.build();
    }

    build(){
        for(let [val,priority] of this.list)
            this.enqueue(val,priority);
    }

    swap(pos1, pos2){
        [this.tree[pos1], this.tree[pos2]] = [this.tree[pos2],this.tree[pos1]]
    }

    enqueue(val, priority){
        this.tree[this.tree.length] = [val, priority];
        let i = this.tree.length - 1, parent = ~~(i/2);
        while(i > 1){
            if(this.tree[parent][1] > this.tree[i][1])
                this.swap(parent,i);
            i = parent;
            parent = ~~(i/2);
        }
    }

    dequeue(){
        let size = this.tree.length - 1, pos = 1;
        if(!size) return;
        let last = this.tree.pop(), deleted = this.tree[pos];
        if(!deleted && last) return last;
        this.tree[pos] = last;
        this.heapify(pos);
        return deleted;
    }

    heapify(pos){

        if(pos > this.tree.length) return;
        let leftPos = 2*pos, rightPos = 2*pos +1;
        let left = this.tree[leftPos] ? this.tree[leftPos][1] : Infinity;
        let right = this.tree[rightPos] ? this.tree[rightPos][1] : Infinity, minVal = null, minIndex = null;
        if(left < right){
            minVal = left;
            minIndex = leftPos;
        }else{
            minVal = right;
            minIndex = rightPos
        }
        if(this.tree[pos][1] > minVal){
            this.swap(pos,minIndex);
            this.heapify(minIndex);
        }
    }

    getTree(){
        console.log(this.tree.slice(1));
    }

    getSize(){
        return this.tree.length - 1;
    }
}
Number of Ways to Arrive at Destination