C++ Dijkstra
\nclass Solution {\n    const int MOD = 1e9+7;\npublic:\n    int countPaths(int n, vector<vector<int>>& roads) {\n        vector<vector<pair<int, int>>> mat(n);
```\nclass Solution {\n    const int MOD = 1e9+7;\npublic:\n    int countPaths(int n, vector<vector<int>>& roads) {\n        vector<vector<pair<int, int>>> mat(n);\n        for (vector<int> road : roads) {\n            mat[road[0]].push_back(make_pair(road[1], road[2]));\n            mat[road[1]].push_back(make_pair(road[0], road[2]));\n        }\n        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;\n        vector<long long> dist(n, LLONG_MAX), count(n);\n        pq.push(make_pair(0, 0));\n        dist[0] = 0; count[0] = 1;\n        while (!pq.empty()) {\n            int u = pq.top().second;\n            if (u==n-1)\n                break;\n            pq.pop();\n            for (pair<int, int> dest : mat[u]) {\n                int v = dest.first;\n                long long weight = dest.second;\n                if (dist[v] == dist[u] + weight) {\n                    count[v] = (count[v] + count[u]) % MOD;\n                }\n                else if (dist[v] > dist[u] + weight) {\n                    dist[v] = dist[u] + weight;\n                    pq.push(make_pair(dist[v], v));\n                    count[v] = count[u];\n                }\n            }\n        }\n        return count[n-1] % MOD;\n    }\n};\n```
[]