[C++]Same as Dijkstra Alogrithm
prerequisite: Dijkstra Algorithm\nvedio link :Dijkstra\'s Algorithm by Striver(Legend)\n\n#define ll long long\nconst int mod = 1e9+7;\nclass Solution {\npublic
**prerequisite: Dijkstra Algorithm**\nvedio link :[Dijkstra\'s Algorithm by Striver(Legend)](https://youtu.be/V6H1qAeB-l4)\n```\n#define ll long long\nconst int mod = 1e9+7;\nclass Solution {\npublic:\n    int countPaths(int n, vector<vector<int>>& roads) {\n        //First create an adjacency list\n        vector<vector<pair<int,int>>> adj(n);\n        for(int i = 0; i < roads.size(); i++){\n            int u = roads[i][0];\n            int v = roads[i][1];\n            int w = roads[i][2];\n            adj[u].push_back({v,w});\n            adj[v].push_back({u,w});\n        }\n        //Now to calculate miminum time to reach the destination let create an array and initialize all the positions to LONG_INT\n        // except starting index\n        vector<ll> time(n,LONG_MAX);\n        time[0] = 0;\n        //Now to store the number of way to reach the node in min time let create another array named way\n        //And initialize all the nodes to zero but the number of way to start from the staring index is 1 so initialize it\n        vector<ll> way(n,0);\n        way[0] = 1;\n        //As usual create an priority queue of pair which stores node and time to reach the current node\n        priority_queue <pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>> > pq;//{time,node}\n        pq.push({0,0});\n        while(!pq.empty()){\n            ll currTime = pq.top().first;\n            int node = pq.top().second;\n            pq.pop();\n            for(auto it: adj[node]){\n                int adjNode = it.first;\n                ll timeTotravel = it.second;\n                // relax adjNode nodes and push in to priority queue\n                // adjNode node ways will be updated with current node ways as\n                // we find a lesser time for adjNode node\n                if(currTime + timeTotravel < time[adjNode]){\n                    time[adjNode] = currTime + timeTotravel;\n                    pq.push({time[adjNode],adjNode});\n                    way[adjNode] = way[node]%mod;\n                }\n                // if current node time + timeTotravel = adjNode node cost then\n                // this is another way to reach the adjNode node with min time\n                // so we update adjNode node ways as ways[adjNode] = (ways[node]+way[adjNode])%mod\n                else if(currTime + timeTotravel == time[adjNode])\n                    way[adjNode] = (way[adjNode]+way[node])%mod;\n            }\n        }\n        return way[n-1];\n    }\n};\n```\n**Time Complexity : O(Total Edge x log(Total Nodes))**\n**space complexity : O(Total Nodes)**
[]