Dijkstra + DP
C++ Solution:\nTime Complexity: O(ElogE)\nSpace complexity: O(V+E)\n\nclass Solution {\npublic:\n    vector<vector<pair<int,int>>> adj1;\n    vector<vector<int>
**C++ Solution:**\n**Time Complexity: O(ElogE)**\n**Space complexity: O(V+E)**\n```\nclass Solution {\npublic:\n    vector<vector<pair<int,int>>> adj1;\n    vector<vector<int>> adj2;\n    vector<int> dis,vis,dp;\n    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;\n    int mod=1e9+7;\n    \n    void dijkstra(int n)\n    {\n        dis[n]=0;\n        q.push({0,n});\n        while(!q.empty())\n        {\n            pair<int,int> tmp=q.top();\n            q.pop();\n            vis[tmp.second]=1;\n            for(auto it:adj1[tmp.second])\n            {\n                if(!vis[it.first] && dis[it.first] > dis[tmp.second]+it.second)\n                {\n                    dis[it.first] = dis[tmp.second]+it.second;\n                    q.push({dis[it.first],it.first});\n                }\n            }\n        }\n    }\n    \n    int go(int src,int n)\n    {\n        if(src>n) return 0;\n        if(src==n) return 1;\n        vis[src]=1;\n        \n        if(dp[src]!=-1) return dp[src];\n        \n        long long int ans=0;\n        for(auto it:adj2[src])\n        {\n            ans = (ans+go(it,n))%mod;\n        }\n        \n        return dp[src]=ans;\n    }\n    \n    int countRestrictedPaths(int n, vector<vector<int>>& edges) {\n        \n        adj1 = vector<vector<pair<int,int>>>(n+1);\n        adj2 = vector<vector<int>>(n+1);\n        dis = vector<int>(n+1,INT_MAX);\n        vis = vector<int>(n+1,0);\n        dp = vector<int>(n+1,-1);\n        \n        for(int i=0;i<edges.size();i++)\n        {\n            adj1[edges[i][0]].push_back({edges[i][1],edges[i][2]});\n            adj1[edges[i][1]].push_back({edges[i][0],edges[i][2]});\n        }\n        \n        dijkstra(n);\n        \n        for(int i=0;i<edges.size();i++)\n        {\n            if(dis[edges[i][0]] > dis[edges[i][1]])\n            {\n                adj2[edges[i][0]].push_back(edges[i][1]);\n            }\n            else if(dis[edges[i][0]] < dis[edges[i][1]])\n            {\n                adj2[edges[i][1]].push_back(edges[i][0]);\n            }\n        }\n        \n        fill(vis.begin(),vis.end(),-1);\n        return go(1,n);\n        \n    }\n};\n```
['Dynamic Programming', 'Depth-First Search', 'Memoization', 'C', 'Shortest Path']