BFS + Dijkstra + Topological Sort Java Solution
Intuition\nAll the restricted path belongs to a DAG, topological sort is a straightforward solution. Calculating the number of paths at the final step requires 
# Intuition\nAll the restricted path belongs to a DAG, topological sort is a straightforward solution. Calculating the number of paths at the final step requires a bit of thinking, topological sort helps in this case since before moving to the next node, it naturally waits for all the incoming edges to finish counting.\n\n# Approach\n- Build the complete graph\n- Dijkstra to get the shortest path from all nodes to `last` node\n- Build the `DAG` from `start` to `last` with all the related restricted paths\n- Topological sort on the `DAG` generated from last step and count paths for each node\n\n# Complexity\n- Time complexity:\n$$O(V + ElogV)$$ bounded by dijkstra\n`E` -> all the nodes\n`V` -> all the edges\n\n- Space complexity:\n$$O(V + E)$$\n\n# Code\n```java []\nclass Solution {\n    class Node {\n        int id;\n        Map<Integer, Integer> neighbors;\n        public Node(int id) {\n            this.id = id;\n            this.neighbors = new HashMap<>();\n        }\n    }\n    private final int MOD = (int)1e9 + 7;\n    private Node[] nodes;\n    private Map<Integer, List<Integer>> adj;\n    private int[] in, distance;\n    public int countRestrictedPaths(int n, int[][] edges) {\n        buildCompleteGraph(edges, n);\n        getShortestPath(n);\n        buildRestrictedPathGraph(0, n - 1);\n        return topologicalSort(n);\n    }\n\n    private int topologicalSort(int n) {\n        long[] ways = new long[n];\n        ways[0] = 1;\n        Queue<Integer> queue = new LinkedList<>();\n        queue.offer(0);\n\n        while (!queue.isEmpty()) {\n            int cur = queue.poll();\n            for (int neighbor: adj.getOrDefault(cur, new ArrayList<>())) {\n                ways[neighbor] = (ways[neighbor] + ways[cur]) % MOD;\n                if (--in[neighbor] == 0) queue.offer(neighbor);\n            }\n        }\n\n        return (int)ways[n - 1];\n    }\n\n    private void buildCompleteGraph(int[][] edges, int n) {\n        this.nodes = new Node[n];\n\n        for (int i = 0; i < n; i++) {\n            nodes[i] = new Node(i);\n        }\n\n        for (int[] edge: edges) {\n            int from = edge[0] - 1, to = edge[1] - 1, cost = edge[2];\n            nodes[from].neighbors.put(to, cost);\n            nodes[to].neighbors.put(from, cost);\n        }\n    }\n\n    private void getShortestPath(int n) {\n        this.distance = new int[n];\n        Arrays.fill(distance, Integer.MAX_VALUE);\n        distance[n - 1] = 0;\n        boolean[] visited = new boolean[n];\n        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);\n        pq.offer(new int[]{n - 1, 0});\n        while (!pq.isEmpty()) {\n            int[] cur = pq.poll();\n            visited[cur[0]] = true;\n            if (cur[1] > distance[cur[0]]) continue;\n            for (int neighbor: nodes[cur[0]].neighbors.keySet()) {\n                if (visited[neighbor]) continue;\n                int newD = cur[1] + nodes[cur[0]].neighbors.get(neighbor);\n                if (newD >= distance[neighbor]) continue;\n                distance[neighbor] = newD;\n                pq.offer(new int[]{neighbor, newD});\n            }\n        }\n    }\n\n    private void buildRestrictedPathGraph(int src, int dst) {\n        int n = distance.length;\n        adj = new HashMap<>();\n        in = new int[n];\n        Queue<Integer> queue = new LinkedList<>();\n        queue.offer(src);\n        boolean[] visited = new boolean[n];\n        visited[src] = true;\n        while (!queue.isEmpty()) {\n            int cur = queue.poll();\n            if (cur == dst) continue;\n            for (int neighbor: nodes[cur].neighbors.keySet()) {\n                if (distance[neighbor] >= distance[cur]) continue;\n                in[neighbor]++;\n                adj.computeIfAbsent(cur, a -> new ArrayList<>()).add(neighbor);\n                if (visited[neighbor]) continue;\n                queue.offer(neighbor);\n                visited[neighbor] = true;\n            }\n        }\n    }\n}\n```
['Java']