✅ C++ || Dijkstra || Priority_Queue || Easy to understand
\n#define ll long long\nclass Solution {\npublic:\n    int MOD = 1e9 + 7;\n    int countPaths(int n, vector<vector<int>>& roads) {\n        vector<pair<ll,ll>> 
```\n#define ll long long\nclass Solution {\npublic:\n    int MOD = 1e9 + 7;\n    int countPaths(int n, vector<vector<int>>& roads) {\n        vector<pair<ll,ll>> adj[n];\n       for(auto it:roads){\n           adj[it[0]].push_back({it[1],it[2]});\n           adj[it[1]].push_back({it[0],it[2]});\n       }\n       \n       priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;\n       vector<ll> dist(n,LONG_MAX), ways(n,0);\n       dist[0] = 0;\n       ways[0] = 1;\n       \n       pq.push({0,0});\n       \n       while(!pq.empty()){\n           ll dis = pq.top().first;\n           ll node = pq.top().second;\n           pq.pop();\n           \n           for(auto it: adj[node]){\n               ll adjNode = it.first;\n               ll edW = it.second;\n               //this is the first time I am coming\n               //with the short distance\n               if(dis + edW < dist[adjNode]){\n                   dist[adjNode] = dis + edW;\n                   pq.push({dis + edW,adjNode});\n                   ways[adjNode] = ways[node];\n               }\n               else if(dis +edW == dist[adjNode]){\n                   ways[adjNode] = (ways[adjNode] + ways[node])%MOD;\n               }\n           }\n       }\n       return ways[n-1];\n    }\n};\n```\n**Don\'t forget to Upvote the post, if it\'s been any help to you**
['C']