✅✅C++ Dijkstra || BFS ||
If Helpful Please Upvoke\n\n\n#define ll long long\nclass Solution{\n    public:\n        int mod = 1e9 + 7;\n    int countPaths(int n, vector<vector < int>> &r
**If Helpful Please Upvoke**\n\n```\n#define ll long long\nclass Solution{\n    public:\n        int mod = 1e9 + 7;\n    int countPaths(int n, vector<vector < int>> &roads){\n        priority_queue<pair<ll, ll>, vector< pair<ll, ll>>, greater<pair<ll, ll>>> pq;\n        pq.push({ 0,0 });\n        vector<ll> dist(n, LLONG_MAX);\n        dist[0] = 0;\n        vector<ll> ways(n, 0);\n        ways[0] = 1;\n\n        vector<pair<ll, ll>> adj[n];\n        for (auto &it: roads){\n            adj[it[0]].push_back({ it[1],\n                it[2] });\n            adj[it[1]].push_back({ it[0],\n                it[2] });\n        }\n            while (!pq.empty()){\n                ll node = pq.top().second;\n                ll dis = pq.top().first;\n                   pq.pop();\n                 for (auto it: adj[node]){\n                    ll wt = it.second;\n                    ll adjnode = it.first;\n                    if (wt + dis < dist[adjnode]){\n                        dist[adjnode] = wt + dis;\n                        ways[adjnode] = ways[node];\n                        pq.push({ dist[adjnode],\n                            adjnode });\n                    }\n                    else if (wt + dis == dist[adjnode])\n                    {\n                        ways[adjnode] = (ways[adjnode] + ways[node]) % mod;\n                    }\n                }\n            }\n\n            return ways[n - 1];\n        }\n    };\n```\n\n**If Helpful PLease Like Or Upvoke**
[]