C++ Solution { Dijkstra + DFS}
\nclass Solution {\npublic:\n    int mod = 1e9 + 7;\n    int dfs(int node, vector<int> &dist, vector<vector<pair<int, int>>> &graph, vector<int> &dp) {\n       
```\nclass Solution {\npublic:\n    int mod = 1e9 + 7;\n    int dfs(int node, vector<int> &dist, vector<vector<pair<int, int>>> &graph, vector<int> &dp) {\n        if(node == dp.size()-1) return 1;\n        if(dp[node] != -1) return dp[node];\n        int ans = 0;\n        for(auto nbr : graph[node]) {\n            if(dist[node] > dist[nbr.first]) {\n                ans = (ans + dfs(nbr.first, dist, graph, dp))%mod;\n            }\n        }\n        return dp[node] = ans;\n    }\n    int countRestrictedPaths(int n, vector<vector<int>>& edges) {\n        vector<vector<pair<int, int>>> graph(n+1);\n        for(auto e : edges) {\n            graph[e[0]].push_back({e[1], e[2]});\n            graph[e[1]].push_back({e[0], e[2]});\n        }\n        vector<int> dist(n+1, INT_MAX);\n        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;\n        pq.push({0, n});\n        dist[n] = 0;\n        while(!pq.empty()) {\n            pair<int, int> p = pq.top();\n            pq.pop();\n            if(dist[p.second] != p.first) \n                continue;\n            for(auto nbr : graph[p.second]) {\n                if(dist[nbr.first] > p.first+nbr.second) {\n                    dist[nbr.first] = p.first+nbr.second;\n                    pq.push({dist[nbr.first], nbr.first});\n                }\n            }\n        }\n        vector<int> dp(n+1, -1);\n        return dfs(1, dist, graph, dp);\n    }\n};\n```
['Depth-First Search', 'C']