Dijkstra's Algorithm
\nclass Solution {\n    int mod = 1_000_000_007;\n    public int countPaths(int n, int[][] roads) {\n        List<int[]>[] graph = new ArrayList[n];\n        \n
```\nclass Solution {\n    int mod = 1_000_000_007;\n    public int countPaths(int n, int[][] roads) {\n        List<int[]>[] graph = new ArrayList[n];\n        \n        for(int i = 0; i < n; i++)\n            graph[i] = new ArrayList<int[]>();\n        \n        for(int[] edge: roads)\n        {\n            int src = edge[0], dest = edge[1], time = edge[2];\n            \n            graph[src].add(new int[]{dest, time});\n            graph[dest].add(new int[]{src, time});\n        }\n        \n        return shortestPath(graph, 0, n);\n    }\n    \n    private int shortestPath(List<int[]>[] graph, int src, int target)\n    {\n        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[1] - b[1]);\n        \n        int[] minCost = new int[target];\n        Arrays.fill(minCost, Integer.MAX_VALUE);\n        \n        long[] ways = new long[target];\n        ways[0] = 1;\n        minCost[0] = 0;\n        \n        pq.offer(new int[]{0, 0});\n        \n        while(!pq.isEmpty())\n        {\n            int[] current = pq.poll();\n            int city = current[0];\n            int curCost = current[1];\n            \n            if(curCost > minCost[city]) \n                continue;\n            \n            for(int[] neighbourData: graph[city])\n            {\n                int neighbour = neighbourData[0], time = neighbourData[1];\n                \n                if(curCost + time < minCost[neighbour])\n                {\n                    minCost[neighbour] = curCost + time;\n                    pq.offer(new int[]{neighbour, minCost[neighbour]});\n                    ways[neighbour] = ways[city];\n                }\n                else if(curCost + time == minCost[neighbour])\n                    ways[neighbour] = (ways[neighbour] + ways[city]) % mod;\n            }\n        }\n        return (int)ways[target - 1];\n    }\n}\n```
['Java']