[C++] [Dijkstra + DFS + DP (Top Down)] [O(ElogE) Time O(E) Space]
```\nclass Solution {\n public:\n  int mod = 1e9 + 7;\n  int countRestrictedPaths(int n, vector>& edges) {\n    vector distanceToLastNode(n + 1, INT_MAX);\n    
```\nclass Solution {\n public:\n  int mod = 1e9 + 7;\n  int countRestrictedPaths(int n, vector<vector<int>>& edges) {\n    vector<int> distanceToLastNode(n + 1, INT_MAX);\n    vector<pair<int, int>> graph[n + 1];\n    for (vector<int>& edge : edges) {\n      graph[edge[0]].push_back({edge[1], edge[2]});\n      graph[edge[1]].push_back({edge[0], edge[2]});\n    }\n    dijkstra(n, graph, distanceToLastNode);\n\n    vector<int> paths(n + 1, -1);\n    return dfs(paths, distanceToLastNode, graph, n);\n  }\n\n private:\n  int dfs(vector<int>& paths, vector<int>& distanceToLastNode,vector<pair<int, int>> graph[], int src) {\n    if (src == 1) return 1;\n    if (paths[src] != -1) return paths[src];\n    int ans = 0;\n    for (auto it : graph[src]) {\n      int v = it.first;\n      if (distanceToLastNode[v] > distanceToLastNode[src]) {\n        ans =(ans % mod + dfs(paths, distanceToLastNode, graph, v) % mod) % mod;\n      }\n    }\n\n    return paths[src] = ans;\n  }\n\n  void dijkstra(int n, vector<pair<int, int>> graph[],vector<int>& distanceToLastNode) {\n    distanceToLastNode[n] = 0;\n    priority_queue<pair<int, int>, vector<pair<int, int>>,greater<pair<int, int>>> pq;\n    pq.push({0, n});\n    while (!pq.empty()) {\n      int u = pq.top().second;\n      pq.pop();\n      for (auto next : graph[u]) {\n        int v = next.first, dis = next.second;\n        if (distanceToLastNode[v] > distanceToLastNode[u] + dis) {\n          distanceToLastNode[v] = distanceToLastNode[u] +dis;\n          pq.push({distanceToLastNode[v], v});\n        }\n      }\n    }\n  }\n};
[]