Simple Java Solution
From the problem statement it was clear we need to apply dijkistra to find shortest path between source and dest.\n2. Well, dijkistra to rescue. Using dijkistra
1. From the problem statement it was clear we need to apply dijkistra to find shortest path between source and dest.\n2. Well, dijkistra to rescue. Using dijkistra we can keep shortest path by keep relaxing the edges. (Cormen lingo).\n3. Catch is, whenver you find a better way to reach a particular vertex update the number of ways we can reach this vertex same as number of ways we can reach parent vertex.\n4. If we arrive at a vetrex, with same time from parent, we will add the parent\'s number of ways to the current vertex\'s number of ways i.e line  dp[v[0]]+=dp[u] in the code\n5. In the End the last veretx will have total number of ways from origin i.e 0\n6. In my solution array named "dp" stores the number of ways from i-th vertex to 0th vertex.\n \n**Similar Problem**: https://leetcode.com/problems/minimum-cost-to-reach-city-with-discounts/\n\nclass Solution {\n    int[] dist;\n    long[] dp;\n\n    public void findDis(Map<Integer, List<int[]>> graph){\n        \n        PriorityQueue<int[]> pq=new PriorityQueue<>((a, b) -> (a[1]- b[1]));\n        pq.add(new int[]{0, 0});\n        dist[0]=0;\n        dp[0]=1;\n        while(!pq.isEmpty()){\n            int[] top=pq.poll();\n            int u=top[0], d=top[1];\n\t\t\tif(dist[u]< d) // new edit\n\t\t\t\tcontinue;\n            for(int[] v: graph.get(u)){\n                if(dist[v[0]] > d + v[1]){\n                    dist[v[0]] = d+v[1];\n                    dp[v[0]]=dp[u];\n                    pq.offer(new int[]{v[0], dist[v[0]]});\n                }else{\n                    if(dist[v[0]] == d+v[1]){\n                        dp[v[0]]+=dp[u];\n                        dp[v[0]]%= 1_000_000_007;\n                    }\n                }\n            }\n        }\n    }\n    \n    public int countPaths(int n, int[][] roads) {\n        dist=new int[n];\n        dp=new long[n];\n        Map<Integer, List<int[]>> graph=new HashMap();\n        Arrays.fill(dist, Integer.MAX_VALUE);\n        for(int i=0;i<n;i++){\n            graph.put(i, new ArrayList());\n            \n        }\n        for(int[] e: roads){\n            graph.get(e[0]).add(new int[]{e[1], e[2]});\n            graph.get(e[1]).add(new int[]{e[0], e[2]});\n        }\n        findDis(graph);\n        \n        return (int)dp[n-1]%1_000_000_007;\n        \n    }  \n}\n**Explanation for point 4 above:** \nlets say we  had arrived at a vertex v previously and recorded its distance from 0 in dist array as dist[v]=40, which means its takes us time=40 from 0 to reach v. lets say the path it followed was 0 -> u1 -> u2 -> v . Here parent vertex of v was u2.\nNow when we arrive at v again but via a different parent, lets call this parent u3 via path 0 -> u1 -> u3 -> v, and the dist[u3]+ Time[u3, v] = 40, which mean this is a whole new way/path of arriving at v from 0 with same time (40), hence we will add the number ways of u3 to number of ways of v i.e dp[v] = dp[v] +dp[u3].\nHope this explanations helped.\nCheers!
[]