All Test Cases|| New Updated solution|| Java
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)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int MOD = (int)(1e9 +7);\n    public int countPaths(int n, int[][] roads) {\n        ArrayList<ArrayList<Pair>> list = new ArrayList<>();\n        for(int i=0;i<n;i++){\n            list.add(new ArrayList<>());\n        }\n        for(int i=0;i<roads.length;i++){\n            list.get(roads[i][0]).add(new Pair(roads[i][1],(long) roads[i][2]));\n            list.get(roads[i][1]).add(new Pair(roads[i][0], (long)roads[i][2]));\n        }\n        PriorityQueue<Pair> pq= new PriorityQueue<>((a,b)->Long.compare( a.d,b.d));\n        pq.add(new Pair(0,0));\n        long[] dist= new long[n];\n        Arrays.fill(dist, Long.MAX_VALUE/2);\n        dist[0]=0;\n        int[] ways = new int[n];\n        ways[0]=1;\n       // int minD=Integer.MAX_VALUE;\n        while(!pq.isEmpty()){\n            Pair p = pq.peek();\n            int node =p.node;\n            long d=p.d;\n            pq.poll();\n            for(Pair np: list.get(node)){\n                int newNode = np.node;\n                long newD =np.d;\n                if(d+newD<dist[newNode]){\n                    ways[newNode]= ways[node];\n                    dist[newNode]=d+newD;\n                    pq.add(new Pair(newNode,d+newD));\n                }\n                else if(d+newD==dist[newNode]){\n                   ways[newNode]=(ways[newNode]  + ways[node])%MOD;\n                }    \n            }\n        }\n        return ways[n-1]%MOD;\n    }\n}\n        \nclass Pair{\n    int node;\n    long d;\n    Pair(){\n\n    }\n    Pair(int node, long d){\n        this.node=node;\n        this.d=d;\n    }\n}\n```
['Breadth-First Search', 'Graph', 'C++', 'Java']