[C++] BFS + DP
\nclass Solution {\npublic:\n    \n    void bfs(int n, const vector<vector<pair<int, int>>>& graph, vector<int>& distances, vector<int>& closest_nodes) {\n     
```\nclass Solution {\npublic:\n    \n    void bfs(int n, const vector<vector<pair<int, int>>>& graph, vector<int>& distances, vector<int>& closest_nodes) {\n        auto cmp = [](const pair<int, int> &a, const pair<int, int> &b) {\n            return a.second > b.second;\n        };\n        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);\n        vector<bool> visited(n+1, false);\n        pq.push({n, 0});\n        \n        while (!pq.empty()) {\n            pair<int, int> current = pq.top();\n            pq.pop();\n            int node = current.first;\n            int dis = current.second;\n            if (visited[node] == true) {\n                continue;\n            }\n            distances[node] = dis;\n            visited[node] = true;\n            closest_nodes.push_back(node);\n            \n            for (pair<int, int> neighbor : graph[node]) {\n                int neighbor_node = neighbor.first;\n                if (visited[neighbor_node] == false) {\n                    pq.push({neighbor_node, dis + neighbor.second});\n                }\n            }\n        }\n    }\n    \n    int countRestrictedPaths(int n, vector<vector<int>>& edges) {\n        vector<vector<pair<int, int>>> graph(n+1);\n        for (const 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        \n        vector<int> distances(n + 1, 0);\n        vector<int> closest_nodes;\n        bfs(n, graph, distances, closest_nodes);\n        \n        vector<long> dp(n+1, 0);\n        dp[1] = 1;\n        int mod = 1e9+7;\n        for (int i = closest_nodes.size() - 1; i >= 0; i--) {\n            int node = closest_nodes[i];\n            for (pair<int, int> neighbor : graph[node]) {\n                int neighbor_node = neighbor.first;\n                if (distances[neighbor_node] < distances[node]) {\n                    dp[neighbor_node] += dp[node];\n                    dp[neighbor_node] %= mod;\n                }\n            }\n        }\n        \n        return dp[n];\n    }\n};\n```
['C']