Bellman Ford + map c++ (slow but it is what it is)
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\nconst int mod = 1e9 + 7;\n    int countPaths(int n, vector<vector<int>>& roads) {\n\n        if(n == 1) return 1;\n\n        vector<long long> dist(n , LLONG_MAX);\n\n        vector<vector<long long>> cnt(n , vector<long long> (n + 1 , 0));\n        unordered_map<long long , int> ans;\n        cnt[0][0] = 1;\n\n        dist[0] = 0;\n\n        for(int i = 1 ; i <= n ; i++) {\n            vector<long long> temp = dist;\n\n            int update = 0;\n            for(auto road : roads) {\n                int u = road[0] , v = road[1] , w = road[2];\n\n                if(dist[u] != LLONG_MAX && temp[v] >= dist[u] + w) {\n                    if(temp[v] > dist[u] + w) {\n                        cnt[v][i] = cnt[u][i - 1];\n                        // update = 1;\n                    }\n                    else if(temp[v] == dist[u] + w) {\n                        cnt[v][i] = (cnt[v][i] +  cnt[u][i - 1]) % mod;\n                    }\n                    temp[v] = dist[u] + w;\n                }\n\n                else if(dist[v] != LLONG_MAX && temp[u] >= dist[v] + w) {\n                    if(temp[u] > dist[v] + w) {\n                        cnt[u][i] = cnt[v][i - 1];\n                        // update = 1;\n                    }\n                    else if(temp[u] == dist[v] + w) {\n                        cnt[u][i] += cnt[v][i - 1] % mod;\n                        cnt[u][i] %= mod;\n                    }\n                    temp[u] = dist[v] + w;\n                }\n            }\n\n            dist = temp;\n           \n            ans[dist[n - 1]] = (ans[dist[n - 1]] +  cnt[n - 1][i]) % mod;\n            \n\n        }\n\n        return ans[dist[n - 1]];\n\n    }\n};\n```
['C++']