import heapq


class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # Create a dummy head node for the merged list
        dummy = ListNode()
        # Initialize the current node to the dummy node
        curr = dummy
        # Create a priority queue to store the first node of each list
        pq = []
        # Iterate over the lists and push the first node of each list to the queue
        for i, node in enumerate(lists):
            # Only push the node if it is not None
            if node:
                # Push a tuple of (node value, list index, node) to the queue
                # The list index is used to break ties when the node values are equal
                heapq.heappush(pq, (node.val, i, node))
        # While the queue is not empty
        while pq:
            # Pop the smallest node from the queue
            _, i, node = heapq.heappop(pq)
            # Append the node to the merged list
            curr.next = node
            # Move the current node to the next node
            curr = curr.next
            # If the node has a next node
            if node.next:
                # Push the next node of the same list to the queue
                heapq.heappush(pq, (node.next.val, i, node.next))
        # Return the head of the merged list
        return dummy.next