Network Breach
The Pentagon's computer network consists of N computers, some of which are linked by direct bidirectional communication channels. To enhance security, the number of these channels has been minimized, ensuring that any two computers can communicate either directly or indirectly through other computers in the network.
The KGB aims to intercept all messages transmitted within the Pentagon's network. To accomplish this, Soviet programmers have developed a virus that, once installed on a computer, relays all information passing through it to the KGB. However, the cost of installing the virus varies from one computer to another. Your task is to determine the set of computers the KGB should infect to minimize the total installation costs.
Input
The first line of the input contains N — the number of computers in the network (1 ≤ N ≤ 500). In the i-th of the next N lines, the numbers of computers directly connected to computer i are listed. Following these lines, there are N integers, each ranging from 1 to 1000, representing the material costs for installing the virus on each computer.
Output
Output the minimum possible total cost.