Graph Algorithms · Hard problem

A planner must connect six warehouses $1$–$6$ with cables. The possible direct cables and their costs (in thousands of dollars) are $12{:}5, 13{:}9, 14{:}3, 23{:}4, 25{:}8, 34{:}6, 35{:}7, 46{:}2, 56{:}10$. What is the minimum total cost to connect all six warehouses?