Min heap
This is just Vanila Dijkstra. I would only note that the min heap is required here not only for the performance, but also for the accuracy.\n\nWe process nodes 
This is just Vanila Dijkstra. I would only note that the min heap is required here not only for the performance, but also for the accuracy.\n\nWe process nodes in the queue from smallest to largest distance, so that we "wait" for all paths with the same distance to reach the node, accumulating the number of ways to reach that node (`cnt`), before moving further from that node.\n\n**C++**\n```cpp\nint countPaths(int n, vector<vector<int>>& roads) {\n    vector<vector<pair<int, int>>> al(n);\n    vector<long> time(n, 0), cnt(n, 1);\n    for (auto &r : roads) {\n        al[r[0]].push_back({r[1], r[2]});\n        al[r[1]].push_back({r[0], r[2]});\n    }\n    priority_queue<pair<long, int>, vector<pair<long, int>>, greater<>> pq;\n    pq.push({0, 0});\n    while (!pq.empty()) {\n        auto[dist, i] = pq.top(); pq.pop();\n            for (auto [j, t] : al[i]) {\n                if (time[j] == 0 || time[j] >= dist + t) {\n                    if (time[j] == dist + t)\n                        cnt[j] = (cnt[j] + cnt[i]) % 1000000007;\n                    else {\n                        time[j] = dist + t;\n                        cnt[j] = cnt[i];\n                        pq.push({time[j], j});\n                    }\n                }\n            }\n    }\n    return cnt[n - 1];\n}\n```
[]