[C++] Dijkstra - Clean & Concise
\nclass Solution {\npublic:\n    int countPaths(int n, vector<vector<int>>& roads) {\n        int mod = 1e9+7;\n        vector<vector<pair<int, int>>> graph(n);
```\nclass Solution {\npublic:\n    int countPaths(int n, vector<vector<int>>& roads) {\n        int mod = 1e9+7;\n        vector<vector<pair<int, int>>> graph(n);\n        for(auto &road: roads) {\n            graph[road[0]].push_back({road[1], road[2]});\n            graph[road[1]].push_back({road[0], road[2]});\n        }\n        \n        vector<long long> distance(n, LONG_MAX);\n        vector<int> path(n, 0);\n        \n        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;\n        pq.push({0, 0});\n        distance[0] = 0;\n        path[0] = 1;\n        \n        while(!pq.empty()) {\n            pair<long long, int> t = pq.top();\n            pq.pop();\n            \n            for(auto &nbr: graph[t.second]) {\n                long long vert = nbr.first;\n                long long edge = nbr.second;\n                \n                if(distance[vert] > distance[t.second] + edge) {\n                    distance[vert] = distance[t.second] + edge;\n                    pq.push({distance[vert], vert});\n                    path[vert] = path[t.second] %mod;\n                }\n                else if(distance[vert] == t.first + edge) {\n                    path[vert] += path[t.second];\n                    path[vert] %= mod;\n                }\n            }\n        }\n        \n        return path[n-1];\n    }\n};\n```
['Dynamic Programming', 'C', 'C++']