1. from collections import defaultdict, deque
2.  
3.  
4. def build_graph(edges):
5.     graph = defaultdict(list)
6.     for edge in edges:
7.         u, v, w = edge
8.         graph[u].append((v, w))
9.         graph[v].append((u, w))
10.     return graph
11.  
12.  
13. def bfs_shortest_paths(graph, src, des):
14.     queue = deque([(src, [src], 0)])  # Updated to include distance
15.     shortest_paths = []
16.     min_dis = float("inf")
17.     while queue:
18.         node, path, dist = queue.popleft()
19.         if node == des:
20.             if dist < min_dis:
21.                 min_dis = dist
22.                 shortest_paths = [[path, dist]]
23.             elif dist == min_dis:
24.                 shortest_paths.append([path, dist])
25.         elif dist <= min_dis:
26.             for neighbor, weight in graph[node]:
27.                 if neighbor not in path:
28.                     queue.append([neighbor, path + [neighbor], dist + weight])
29.     return shortest_paths
30.  
31.  
32. def find_shortest_paths(edges, source, destination):
33.     graph = build_graph(edges)
34.     shortest_paths = bfs_shortest_paths(graph, source, destination)
35.     return shortest_paths
36.  
37.  
38. edges = [[1, 2, 5], [1, 3, 2], [3, 4, 1], [1, 4, 6], [3, 5, 5]]
39. source = 1
40. for destination in range(2, 6):
41.     shortest_paths = find_shortest_paths(edges, source, destination)
42.     print("Shortest paths between", source, "and", destination, ":", shortest_paths)
43.