Modified Dijkstra's, No extra DP / BFS / DFS
\n\n# Code\ncpp []\n#define ll long long \nclass Solution {\npublic:\n    int countRestrictedPaths(int n, vector<vector<int>>& edges) {\n        ll M = 1e9 + 7;
\n\n# Code\n```cpp []\n#define ll long long \nclass Solution {\npublic:\n    int countRestrictedPaths(int n, vector<vector<int>>& edges) {\n        ll M = 1e9 + 7;\n        vector<vector<pair<ll,ll>>> adjMat(n+1, vector<pair<ll,ll>>());\n        for(auto edge: edges){\n            adjMat[edge[0]].push_back({edge[1], edge[2]});\n            adjMat[edge[1]].push_back({edge[0], edge[2]});\n        }\n\n        vector<ll> minDist(n+1, -1);\n        vector<ll> path(n+1, 0);\n\n        set<pair<ll,ll>> pq;\n\n        minDist[n] = 0;\n        path[n] = 1;\n        pq.insert({minDist[n], n});\n\n        while(!pq.empty()){\n            ll curNode = (*pq.begin()).second;\n            ll curDist = (*pq.begin()).first;\n            pq.erase(pq.begin());\n            for(pair<ll,ll> adjNode : adjMat[curNode]){\n                ll newDist = curDist + adjNode.second;\n                if(minDist[adjNode.first] == -1 || minDist[adjNode.first] >= newDist){\n                    pq.erase({minDist[adjNode.first], adjNode.first});\n                    minDist[adjNode.first] = newDist;\n                    pq.insert({minDist[adjNode.first], adjNode.first});\n                }\n                if(minDist[adjNode.first] > curDist){\n                    path[adjNode.first] += path[curNode];\n                    path[adjNode.first]%= M;\n                }\n            }\n        }\n        return path[1];\n    }\n};\n```
['C++']