[C++] | Dijkstra
\nclass Solution {\npublic:\n    int count = 0, MOD = 1e9 + 7;\n    int countPaths(int n, vector<vector<int>>& r) {\n        vector<pair<long long, long long>> 
```\nclass Solution {\npublic:\n    int count = 0, MOD = 1e9 + 7;\n    int countPaths(int n, vector<vector<int>>& r) {\n        vector<pair<long long, long long>> A[n];\n        vector<long long> dist(n, LONG_MAX), ways(n);\n        ways[0] = 1;\n        priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq;\n        for(auto& a: r){\n            A[a[0]].push_back({a[1], a[2]});\n            A[a[1]].push_back({a[0], a[2]});\n        }\n        pq.push({0, 0});\n        dist[0] = 0;\n        while(!pq.empty()){\n            auto [cost, node] = pq.top();\n            pq.pop();\n            if(cost > dist[node]) continue;\n            for(auto& [to, time]: A[node]){\n                if(dist[to] > time + dist[node]){\n                    dist[to] = time + dist[node];\n                    ways[to] = ways[node];\n                    pq.push({dist[to], to});\n                }\n                else if(dist[to] == time + dist[node])\n                    ways[to] += ways[node], ways[to] %= MOD;\n            }\n        }\n        return max(1, (int)ways[n - 1]);\n    }\n};\n```
['C', 'C++']