Java-Using Edge Class
Please UpVote if you liked my solution. \uD83D\uDE42\nIf you didn\'t understand,Mail me @piyushchhawachharia@gmail.com and I\'ll explain that to you one-on-one.
Please UpVote if you liked my solution. \uD83D\uDE42\nIf you didn\'t understand,Mail me @piyushchhawachharia@gmail.com and I\'ll explain that to you one-on-one.\nThe Coding Community Always Sticks Together! :)\n\n# Code\n```\nclass Solution {\n    static class Edge{\n        int vtc;\n        int nbr;\n        int wt;\n        Edge(int vtc,int nbr,int wt){\n            this.vtc=vtc;\n            this.nbr=nbr;\n            this.wt=wt;\n        }\n    }\n    static class Pair implements Comparable<Pair>{\n        int vtc;\n        int wt;\n        Pair(int vtc,int wt){\n            this.vtc=vtc;\n            this.wt=wt;\n        }\n        public int compareTo(Pair o){\n            return this.wt-o.wt;\n        }\n    }\n    public int countPaths(int n, int[][] roads) {\n        int mod=(int)Math.pow(10,9)+7;\n        ArrayList<Edge>[] graph=new ArrayList[n];\n        for(int i=0;i<n;i++){\n            graph[i]=new ArrayList<>();\n        }\n\n        for(int i=0;i<roads.length;i++){\n            graph[roads[i][0]].add(new Edge(roads[i][0],roads[i][1],roads[i][2]));\n            graph[roads[i][1]].add(new Edge(roads[i][1],roads[i][0],roads[i][2]));\n        }\n        int dist[]=new int[n];\n        Arrays.fill(dist,Integer.MAX_VALUE);\n        dist[0]=0;\n        int count[]=new int[n];\n        count[0]=1;\n        PriorityQueue<Pair> pq=new PriorityQueue<>();\n        pq.add(new Pair(0,0));\n\n        while(pq.size()>0){\n            Pair rm=pq.remove();\n\n\n            for(Edge e:graph[rm.vtc]){\n                if((rm.wt+e.wt)<dist[e.nbr]){\n                    dist[e.nbr]=rm.wt+e.wt;\n                    pq.add(new Pair(e.nbr,dist[e.nbr]));\n                    count[e.nbr]=count[rm.vtc];\n                }\n                else if((rm.wt+e.wt==dist[e.nbr])){\n                    count[e.nbr]=(count[e.nbr]+count[rm.vtc])%mod;\n                }\n            }\n        }\n        for(int i=0;i<n;i++){\n            System.out.println(dist[i]);\n        }\n        return (int)(count[n-1]%mod);\n    }\n}\n```
['Java']