C++ Solution O(n^3) || Floyd Warshall || DP
\n#define ll long long int\nconst ll mod= 1e9+7;\nclass Solution {\npublic:\n    int countPaths(int n, vector<vector<int>>& roads) {\n        ll dp[n][n][2]; \n
```\n#define ll long long int\nconst ll mod= 1e9+7;\nclass Solution {\npublic:\n    int countPaths(int n, vector<vector<int>>& roads) {\n        ll dp[n][n][2]; \n        // dp[i][j][0] stores minimum distance and dp[i][j][1] stores number of ways to reach     with the minimum distance dp[i][j][0]\n        for(ll i=0; i<n; i++){\n            for(ll j=0; j<n; j++){\n                if(i!=j){\n                    dp[i][j][0] = 1e13;\n                    dp[i][j][1]=0;\n                }\n                else\n                {\n                    dp[i][j][0]=0;\n                    dp[i][j][1]=1;\n                }\n            }\n        }\n        for(ll i=0; i<roads.size(); i++){\n            dp[roads[i][0]][roads[i][1]][0]=roads[i][2];\n            \n            dp[roads[i][1]][roads[i][0]][0]=roads[i][2];\n            dp[roads[i][0]][roads[i][1]][1]=1;\n            \n            dp[roads[i][1]][roads[i][0]][1]=1;\n        }\n        for(ll mid=0; mid<n; mid++){\n            for(ll i=0; i<n; i++){\n                for(ll j=0; j<n; j++){\n                    if(i!=mid && j!=mid){\n                        if(dp[i][mid][0]+dp[mid][j][0]<dp[i][j][0]){\n                            dp[i][j][0]=dp[i][mid][0]+dp[mid][j][0];\n                            dp[i][j][1] = (dp[i][mid][1]*dp[mid][j][1])%mod;\n                        }\n                        else if(dp[i][j][0]==dp[i][mid][0]+dp[mid][j][0]){\n                            dp[i][j][1] = (dp[i][j][1]+dp[i][mid][1]*dp[mid][j][1])%mod;\n                        }\n                    }\n                }\n            }\n        }\n        return dp[n-1][0][1];\n    }\n};\n```
[]