class Solution {
    int minPathSum = Integer.MAX_VALUE;
    public List<List<Integer>> allShortestPaths(int[][] edges, int start, int end) {
        Map<Integer, Map<Integer, Integer>> graph = buildGraph(edges);
        List<List<Integer>> results = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        dfs(start, end, visited, graph, new LinkedList<>(), results, 0);
        return results;
    }
    
    private void dfs(int current, int end, Set<Integer> visited, Map<Integer, Map<Integer, Integer>> graph, List<Integer> path, List<List<Integer>> results, int pathSum) {
        path.add(current);
        if (current == end) {
            if (minPathSum > pathSum) {
                results.clear();
                results.add(new LinkedList<>(path));
                minPathSum = pathSum;
            } else if (pathSum == minPathSum) {
                results.add(new LinkedList<>(path));
            }
            path.remove(path.size() - 1);
            return;
        }
        visited.add(current);
        for (Map.Entry<Integer, Integer> entry : graph.getOrDefault(current, new HashMap<>()).entrySet()) {
            if (!visited.contains(entry.getKey())) {
                dfs(entry.getKey(), end, visited, graph, path, results, pathSum + entry.getValue());
            }
        }
        path.remove(path.size() - 1);
        visited.remove(current);
    }    
    private Map<Integer, Map<Integer, Integer>> buildGraph(int[][] edges) {
        Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            graph.putIfAbsent(edge[0], new HashMap<>());
            graph.putIfAbsent(edge[1], new HashMap<>());
            graph.get(edge[0]).put(edge[1], edge[2]);
            graph.get(edge[1]).put(edge[0], edge[2]);
        }
        return graph;
    }
}

 1 public List<Integer> shortestPaths(int[][] edges, int start, int end) {
 2         Map<Integer, Integer> currentValue = new HashMap<>();
 3         currentValue.put(start, 0);
 4         Map<Integer, Integer> parentMap = new HashMap<>();
 5         
 6         Map<Integer, Map<Integer, Integer>> graph = buildGraph(edges);
 7         Queue<int[]> minQueue = new PriorityQueue<>((arr1, arr2) -> arr1[0] - arr2[0]);
 8         minQueue.offer(new int[] {0, start});
 9         while (!minQueue.isEmpty()) {
10             int[] current = minQueue.poll();
11             if (current[1] == end) {
12                 return getPath(parentMap, end);
13             }
14             
15             for (Map.Entry<Integer, Integer> neighbor : graph.getOrDefault(current[1], new HashMap<>()).entrySet()) {
16                 int neighborValue = currentValue.getOrDefault(neighbor.getKey(), Integer.MAX_VALUE);
17                 if (current[0] + neighbor.getValue() < neighborValue) {
18                     currentValue.put(neighbor.getKey(), current[0] + neighbor.getValue());
19                     parentMap.put(neighbor.getKey(), current[1]);
20                     minQueue.offer(new int[] {current[0] + neighbor.getValue(), neighbor.getKey()});
21                 }
22             }
23         }
24         return new LinkedList<>();
25     }
26     
27     private List<Integer> getPath(Map<Integer, Integer> parentMap, int end) {
28         List<Integer> list = new LinkedList<>();
29         list.add(0, end);
30         while (parentMap.containsKey(end)) {
31             end = parentMap.get(end);
32             list.add(0, end);
33         }
34         return list;
35     }