JAVA STEP BY STEP EXPLAINED✅✅ || SIMPLEST SOLUTION😀✌️
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ --> O(m + n log n).\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ --> O(m + n)\n![Screenshot_20230205_171246.png](https://assets.leetcode.com/users/images/b3cedf6e-69d2-4339-a4a6-29d2bb7c8243_1693378471.3360426.png)\n\n\n# Code\n```\nclass Pair {\n    long first;\n    long second;\n\n    Pair(long first, long second) {\n        this.first = first;\n        this.second = second;\n    }\n}\n\nclass Solution {\n    public int countPaths(int n, int[][] roads) {\n        \n        // Create an adjacency list to represent the graph\n        ArrayList<ArrayList<Pair>> adj = new ArrayList<>();\n\n        // Initialize the adjacency list\n        for (int i = 0; i < n; i++) {\n            adj.add(new ArrayList<>());\n        }\n\n        int m = roads.length;\n\n        // Populate the adjacency list with road information\n        for (int i = 0; i < m; i++) {\n            adj.get(roads[i][0]).add(new Pair(roads[i][1], roads[i][2]));\n            adj.get(roads[i][1]).add(new Pair(roads[i][0], roads[i][2]));\n        }\n\n        // Create a priority queue for Dijkstra\'s algorithm\n        PriorityQueue<Pair> pq = new PriorityQueue<>((Pair1, Pair2) -> Long.compare(Pair1.first, Pair2.first));\n\n        // Initialize arrays for distances and ways\n        long dist[] = new long[n];\n        long ways[] = new long[n];\n        long mod = (int)(1e9 + 7);\n\n        // Initialize distance and ways arrays\n        for (int i = 0; i < n; i++) {\n            dist[i] = Long.MAX_VALUE;\n            ways[i] = 0;\n        }\n\n        // Starting node has distance 0 and one way to reach it\n        dist[0] = 0;\n        ways[0] = 1;\n\n        pq.add(new Pair(0, 0));\n\n        while (pq.size() != 0) {\n            long dis = pq.peek().first;\n            long node = pq.peek().second;\n            pq.remove();\n\n            // Explore neighboring nodes\n            for (Pair it : adj.get((int) node)) {\n                long adjNode = it.first;\n                long edW = it.second;\n\n                // If a shorter path is found, update distance and ways\n                if (dis + edW < dist[(int) adjNode]) {\n                    dist[(int) adjNode] = dis + edW;\n                    pq.add(new Pair(dis + edW, adjNode));\n                    ways[(int) adjNode] = ways[(int) node];\n                } else if (dis + edW == dist[(int) adjNode]) {\n                    // If multiple paths with the same length are found, add their ways\n                    ways[(int) adjNode] = (ways[(int) adjNode] + ways[(int) node]) % mod;\n                }\n            }\n        }\n\n        // Return the number of ways to reach the last node modulo mod\n        return (int)(ways[n - 1] % mod);\n    }\n}\n\n```
['Breadth-First Search', 'Graph', 'Shortest Path', 'Java']