C++ solution|| Dijkastra ALGO
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int countPaths(int n, vector<vector<int>>& roads) {\n         vector<pair<int, int>> adj[n];  // Create adjacency list\n        for (auto& nbr : roads) {\n            adj[nbr[0]].push_back({nbr[1], nbr[2]});\n        adj[nbr[1]].push_back({nbr[0], nbr[2]});\n        }\n\n        priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq;\n        vector<long long> dist(n, LLONG_MAX);  \n        vector<long long> ways(n, 0);\n        dist[0] = 0;\n        ways[0] = 1;\n        pq.push({0, 0});\n        const long long mod = 1e9 + 7;\n\n        while (!pq.empty()) {\n            long long dis = pq.top().first;\n            long long node = pq.top().second;\n            pq.pop();\n\n            for (auto& it : adj[node]) {\n                long long adjNode = it.first;\n                long long edw = it.second;\n\n                if (dis + edw < dist[adjNode]) {\n                    dist[adjNode] = dis + edw;\n                    pq.push({dis + edw, adjNode});\n                    ways[adjNode] = ways[node];\n                } else if (dis + edw == dist[adjNode]) {\n                    ways[adjNode] = (ways[adjNode] + ways[node]) % mod;\n                }\n            }\n        }\n\n        return ways[n - 1] % mod;\n\n    }\n};\n```
['C++']