[C++] : Using dikstra + toposort(DAG) + DP
\n#define ll long long int\nconst ll M = 1e9 + 7;\n#define MOD_ADD(a,b,m) ((a % m) + (b % m)) % m\n\nclass Solution {\npublic:\n    \n    static bool compare(pa
```\n#define ll long long int\nconst ll M = 1e9 + 7;\n#define MOD_ADD(a,b,m) ((a % m) + (b % m)) % m\n\nclass Solution {\npublic:\n    \n    static bool compare(pair<ll,ll> a, pair<ll,ll> b)\n    {\n        return a.second > b.second; // min heap\n    }\n    \n    vector<ll> dikstra(ll src, vector<vector<pair<ll,ll>>> &adj, ll n)\n    {\n        vector<ll> dis(n, 1e18); //1e18 is imp here\n        vector<bool> vis(n, 0);\n    \n        priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, function<bool(pair<ll,ll>, pair<ll,ll>)>> Q(compare);\n        \n        Q.push({src, 0});\n        \n        while(!Q.empty())\n        {\n            pair<ll,ll> now = Q.top(); Q.pop();\n            \n            ll u = now.first;\n            \n            if(vis[u]) continue;\n            vis[u] = 1;\n            dis[u] = now.second;\n            \n            for(auto x : adj[u])\n            {\n                ll v = x.first;\n                ll w = x.second;\n                \n                if(dis[v] > dis[u] + w)\n                {\n                    dis[v] = dis[u] + w;\n                    Q.push({v, dis[v]});\n                }\n            }\n        }\n    \n        return dis;\n    }\n    \n    vector<ll> toposort(vector<vector<ll>> &adj, ll n)\n    {\n        vector<ll> ans;\n        ll indegree[n]; memset(&indegree, 0x00, sizeof(indegree));\n        for(int u = 0; u < n; u++)\n        {\n            for(auto v : adj[u])\n                indegree[v]++;\n        }\n        \n        \n        queue<ll> q;\n        for(int i = 0; i < n; i++) if(!indegree[i]) q.push(i);\n        \n        while(!q.empty())\n        {\n            ll u = q.front(); q.pop();\n            ans.push_back(u);\n            \n            for(auto v : adj[u])\n            {\n                indegree[v]--;\n                if(!indegree[v]) q.push(v);\n            }\n        }\n        \n        return ans;\n    }\n    \n    int countPaths(int n, vector<vector<int>>& roads) \n    {\n        vector<vector<pair<ll,ll>>> adj(n);\n        for(auto e : roads)\n        {\n            adj[e[0]].push_back({e[1], e[2]});\n            adj[e[1]].push_back({e[0], e[2]});\n        }\n        \n        vector<ll> dis = dikstra(0, adj, n);\n        \n        vector<vector<ll>> DAG(n);\n        for(auto e : roads)\n        {\n            ll u = e[0];\n            ll v = e[1];\n            ll w = e[2];\n            \n            if(dis[u] + w == dis[v])\n            {\n                //include this edge u -> v\n                DAG[u].push_back(v);\n            }\n            else if(dis[v] + w == dis[u])\n            {\n                //include this edge v -> u\n                DAG[v].push_back(u);\n            }\n        }\n        \n        vector<ll> topo = toposort(DAG, n);\n        \n        ll dp[n]; memset(&dp, 0x00, sizeof(dp));\n        dp[n - 1] = 1;\n        \n        for(int i = n - 1; i >= 0; i--)\n        {\n            ll u = topo[i];\n            if(u == n - 1) continue;\n            \n            for(auto v : DAG[u]) dp[u] = MOD_ADD(dp[u], dp[v], M);\n        }\n        \n        return dp[0];\n        \n    }\n};\n```
['Dynamic Programming', 'Topological Sort']