Striver's Corrected Code : Java 100% Working
\n# Complexity\n- Time complexity:\nO(n*log(n))\n\n- Space complexity:\nO(n)\n\n# Code\n\n  class Pair{\n    long first;\n    long second;\n    public Pair(long
\n# Complexity\n- Time complexity:\n$$O(n*log(n))$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\n  class Pair{\n    long first;\n    long second;\n    public Pair(long dis,long node){\n        this.first=dis;\n        this.second=node;\n    }\n}\nclass Solution {\n   public int countPaths(int n, int[][] roads) {\n        ArrayList<ArrayList<Pair>> al = new ArrayList<>();\n        for(int i=0;i<n;i++){\n            al.add(new ArrayList<>());\n        }\n        for(int x[]:roads){\n            al.get(x[0]).add(new Pair(x[1],x[2]));\n            al.get(x[1]).add(new Pair(x[0],x[2]));\n        }\n        PriorityQueue<Pair> pq = new PriorityQueue<>((a,b) -> Long.compare(a.second, b.second));\n        long dist[]=new long[n];\n        long ways[]=new long[n];\n        for(int i=0;i<n;i++){\n            dist[i]=Long.MAX_VALUE;\n            ways[i]=0;\n        }\n        dist[0]=0;\n        ways[0]=1;\n        pq.add(new Pair(0,0));\n        int mod = (int)(1e9+7);\n        while(!pq.isEmpty()){\n            Pair temp = pq.poll();\n            long dis = temp.second;\n            int node = (int)(temp.first);\n            for(Pair it : al.get(node)){\n                int adjnode = (int)it.first;\n                long dw = it.second;\n                if(dis+dw<dist[adjnode]){\n                    dist[adjnode]=dis+dw;\n                    pq.add(new Pair(adjnode,dis+dw));\n                    ways[adjnode]=ways[node];\n                }else if(dis+dw == dist[adjnode]){\n                    ways[adjnode]= (ways[adjnode]+ways[node])%mod;\n                }\n            }\n        }\n        return (int)(ways[n-1]%mod);\n    }\n}\n```
['Dynamic Programming', 'Graph', 'Topological Sort', 'Shortest Path', 'C++', 'Java', 'Python3']