from collections import defaultdict, deque


def build_graph(edges):
    graph = defaultdict(list)
    for edge in edges:
        u, v, w = edge
        graph[u].append((v, w))
        graph[v].append((u, w))
    return graph


def bfs_shortest_paths(graph, src, des):
    queue = deque([(src, [src], 0)])  # Updated to include distance
    shortest_paths = []
    min_dis = float("inf")
    while queue:
        node, path, dist = queue.popleft()
        if node == des:
            if dist < min_dis:
                min_dis = dist
                shortest_paths = [[path, dist]]
            elif dist == min_dis:
                shortest_paths.append([path, dist])
        elif dist <= min_dis:
            for neighbor, weight in graph[node]:
                if neighbor not in path:
                    queue.append([neighbor, path + [neighbor], dist + weight])
    return shortest_paths


def find_shortest_paths(edges, source, destination):
    graph = build_graph(edges)
    shortest_paths = bfs_shortest_paths(graph, source, destination)
    return shortest_paths


edges = [[1, 2, 5], [1, 3, 2], [3, 4, 1], [1, 4, 6], [3, 5, 5]]
source = 1
for destination in range(2, 6):
    shortest_paths = find_shortest_paths(edges, source, destination)
    print("Shortest paths between", source, "and", destination, ":", shortest_paths)