Easy C++ Solution
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:O(N){dfs}+O(V+E){djksta}\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n//In this question first we need to find the minimum weight(smiliar to minimum distance) it takes to reach the end node from every node\n// after that we traverse from first node in search of a valid path and we keep a count and return it\nclass Solution {\npublic:\n    const int MOD = 1e9 + 7;\n\n    int dfs(int node, int end, vector<int>& dis, unordered_map<int, vector<pair<int, int>>>& adj, vector<int>& dp) {\n        if (node == end) {\n            return dp[node]=1;        // when we reach the final destination we retrun 1 which signifies a path found\n        }\n\n        if(dp[node]!=-1)return dp[node];\n\n        int count = 0;\n\n        for (auto u : adj[node]) {\n            if (dis[node] > dis[u.first]) {            // we only move forward when condition is satisfied\n                int path = dfs(u.first, end, dis, adj, dp);\n                count = (count + path) % MOD;  // Update count with modular arithmetic.\n            }\n        }\n\n        return dp[node]=count;\n    }\n\n    int countRestrictedPaths(int n, vector<vector<int>>& edges) {\n        unordered_map<int, vector<pair<int, int>>> adj;\n\n        for (int i = 0; i < edges.size(); i++) {\n            int u = edges[i][0];\n            int v = edges[i][1];\n            int wt = edges[i][2];\n\n            adj[u].push_back({v, wt});\n            adj[v].push_back({u, wt}); // Assuming an undirected graph\n        }\n\n        vector<int> dis(n + 1, INT_MAX);\n        dis[n] = 0;\n\n        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;\n        pq.push({0, n}); // Push the starting node with distance 0\n\n        while (!pq.empty()) {\n            int dist = pq.top().first;\n            int node = pq.top().second;\n            pq.pop();\n\n            for (auto u : adj[node]) {\n                int adjNode = u.first;\n                int adjDist = u.second;\n\n                if (dis[adjNode] > dist + adjDist) {\n                    dis[adjNode] = dist + adjDist;\n                    pq.push({dis[adjNode], adjNode});\n                }\n            }\n        }\n        // calling dfs from node 1 to last node \n        //this will return no of restricated path\n        vector<int> dp(n + 1, -1);      // dp array\n        int i = 1;                      //starting from node 1\n        return dfs(i, n, dis, adj, dp);\n    }\n};\n```
['Dynamic Programming', 'Depth-First Search', 'Shortest Path', 'C++']