Dijkstra + DFS | C++
\nconst int mod = 1e9+7;\n\tint dp[20005];\n    int countRestrictedPaths(int n, vector<vector<int>>& edges) {\n        \n        memset(dp,-1,sizeof(dp));\n    
```\nconst int mod = 1e9+7;\n\tint dp[20005];\n    int countRestrictedPaths(int n, vector<vector<int>>& edges) {\n        \n        memset(dp,-1,sizeof(dp));\n        vector<vector<pair<int,int>>> adj(n+1);\n        \n        //building the adjacency matrix\n        for(int i = 0; i<edges.size(); i++){\n            adj[edges[i][0]].push_back({edges[i][1],edges[i][2]});\n            adj[edges[i][1]].push_back({edges[i][0],edges[i][2]});\n        }\n        \n        //dijkstra for nth node\n        vector<int> distTo(n+1,INT_MAX);\n        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;\n        \n        pq.push({0,n});\n        distTo[n] = 0;\n        \n        while(!pq.empty()){\n            int node = pq.top().second;\n            int distance = pq.top().first;\n            pq.pop();\n            \n            for(auto x : adj[node]){\n                int adjNode = x.first;\n                int nextDist = x.second;\n                if(distance+nextDist < distTo[adjNode]){\n                    distTo[adjNode] = distance+nextDist;\n                    pq.push({distTo[adjNode],adjNode});\n                }\n            }\n        }\n        \n        vector<int> dp(n + 1, -1);\n        return dfs(adj,1,n,distTo);\n    }\n    \n    int dfs(vector<vector<pair<int,int>>>& adj, int s, int n, vector<int> &distTo){\n        \n        if(s == n) return 1;\n        if(dp[s] != -1) return dp[s];\n        \n        int ans = 0;\n        \n        for(auto x : adj[s]){\n            if(distTo[s]>distTo[x.first]){\n                ans = (ans+dfs(adj,x.first,n,distTo))%mod;\n            }\n        }\n        return dp[s] = ans%mod; \n        \n    }\n```
['Depth-First Search', 'C']