No_of_ways_to_arrive_at_destination

class Solution {
public:
    int countPaths(int n, vector<vector<int>>& roads) {
        vector<long long> dist(n, LLONG_MAX), ways(n, 0);
        vector<pair<long long,long long>> adj[n];

        for (auto y: roads) {
            adj[y[0]].push_back({y[1],y[2]});
            adj[y[1]].push_back({y[0], y[2]});
        }
        long long mod = (long long)(1e9 + 7);

        priority_queue<pair<long long,long long>, vector<pair<long long,long long>>, greater<pair<long long,long long>>>pq;
        // src
        dist[0] = 0;
        ways[0] = 1;
        pq.push({dist[0], 0});

        while (!pq.empty()) {
            long long u = pq.top().second;
            long long ed = pq.top().first;
            pq.pop();
            if (ed > dist[u]) continue;

            for (auto nei: adj[u]) {
                int v = nei.first;
                int wei = nei.second;

                if (dist[v] > dist[u] + wei) {
                    dist[v] = dist[u] + wei;
                    ways[v] = ways[u];
                    pq.push({dist[v], v});

                }
                else if (dist[v] == dist[u] + wei) {
                    ways[v] = (ways[v] + ways[u]) % (mod);
                }

            }
        }

        return ways[n - 1] % mod;


    }
};