Dijkstra + Keeping Count of the number of ways
\ntypedef long long ll;\n    typedef pair<long long, long long> ppl;\n    int countPaths(int n, vector<vector<int>>& roads) {\n        int mod = (1e9+7);\n     
```\ntypedef long long ll;\n    typedef pair<long long, long long> ppl;\n    int countPaths(int n, vector<vector<int>>& roads) {\n        int mod = (1e9+7);\n        vector<ll> dist(n,LLONG_MAX);\n        vector<int> ways(n,0);\n        priority_queue<ppl, vector<ppl>, greater<ppl>> pq;\n        \n        dist[0] = 0; ways[0]=1; pq.push({0,0});\n        \n        vector<ppl> adj[n];\n        \n        //making adjacency list\n        for(auto x : roads){\n            adj[x[0]].push_back({x[1],x[2]});\n            adj[x[1]].push_back({x[0],x[2]});\n        }\n        \n        while(!pq.empty()){\n            ll distance = pq.top().first;\n            ll node = pq.top().second;\n            pq.pop();\n            for(auto x : adj[node]){\n                ll adjNode = x.first;\n                ll nextDist = x.second;\n                \n                if(distance+nextDist < dist[adjNode]){\n                    dist[adjNode] = distance+nextDist;\n                    ways[adjNode] = ways[node];\n                    pq.push({dist[adjNode],adjNode});\n                } else if(distance+nextDist == dist[adjNode]){\n                    ways[adjNode] = (ways[adjNode]+ways[node])%mod;\n                }\n            }\n        }\n        \n        return ways[n-1];\n    }\n```
['C']