Striver's Approach  Passing all test cases
Intuition\n Describe your first thoughts on how to solve this problem. \nWe start at one node (node 0) and want to figure out the best way to reach all other no
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe start at one node (node 0) and want to figure out the best way to reach all other nodes while also keeping track of the number of different paths we can take. To do this, we use a method called Dijkstra\'s algorithm, which helps us find the shortest routes efficiently. As we explore these routes, we also count how many ways we can reach each node. When we reach our destination node (node n\u22121), we have the total count of ways to get there.\n\n# Approach \nSimple Dijkstra\'s Algorithm + BFS + Heap(Priority Queue)\nThis approach uses Dijkstra\'s algorithm and additional data structures to efficiently count paths and update no of ways.\n# Complexity\n- Time complexity: O((n+E)logn) for Dijkstra\'s algorithm with a priority queue.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n+E) for storing the graph and ways count\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nimport java.util.*;\n\nclass Solution {\n    public int countPaths(int n, int[][] roads) {\n        PriorityQueue<Pair> q = new PriorityQueue<>((x, y) -> Long.compare(x.a, y.a));\n        List<List<Pair>> adj = new ArrayList<>();\n        for (int i = 0; i < n; i++) {\n            adj.add(new ArrayList<>());\n        }\n        for (int[] ar : roads) {\n            adj.get(ar[0]).add(new Pair(ar[1], ar[2])); // node wt\n            adj.get(ar[1]).add(new Pair(ar[0], ar[2]));\n        }\n        long[] dis = new long[n];\n        int[] ways = new int[n];\n\n        Arrays.fill(dis, Long.MAX_VALUE / 2);\n        dis[0] = 0;\n        ways[0] = 1;\n        q.add(new Pair(0, 0));\n\n        while (!q.isEmpty()) {\n            long pd = q.peek().a;\n            long node = q.peek().b;\n            q.remove();\n            for (Pair i : adj.get((int) node)) {\n                long edgewt = i.b;\n                long adjnode = i.a;\n                if (edgewt + pd < dis[(int) adjnode]) {\n                    dis[(int) adjnode] = edgewt + pd;\n                    q.add(new Pair(dis[(int) adjnode], adjnode));\n                    ways[(int) adjnode] = ways[(int) node];\n                } else if (edgewt + pd == dis[(int) adjnode]) {\n                    ways[(int) adjnode] = (ways[(int) adjnode] + ways[(int) node]) % ((int) 1e9 + 7); // Corrected ways count\n                }\n            }\n        }\n\n        return ways[n - 1] % ((int) 1e9 + 7);\n    }\n}\n\nclass Pair {\n    long a; // distance\n    long b; // node\n\n    Pair(long a, long b) {\n        this.a = a;\n        this.b = b;\n    }\n}\n\n```
['Breadth-First Search', 'Heap (Priority Queue)', 'Java']