Angry Programmer |
The computer of your boss and the central server are in the same network, which is composed of many machines (computers) and wires linking pairs of those machines. There is at most one wire between any pair of machines and there can be pairs of machines without a wire between them.
To accomplish your objective, you can destroy machines and wires, but you can't destroy neither the computer of your boss nor the central server, because those machines are monitored by security cameras. You have estimated the cost of blowing up each machine and the cost of cutting each wire in the network.
The input consists of several test cases. Each test case is represented as follows:
For each test case, print a line with the minimum cost of interrupting the communication between the computer of your boss and the central server.
You want to determine the minimum cost of interrupting the communication between your boss' computer and the central server. Two computers A
Input
The end of the input is specified by a line with the string ``0 0''.
Suppose that the machines have distinct identifiers.
Output
Sample Input
4 4
3 5
2 2
1 2 3
1 3 3
2 4 1
3 4 3
4 4
3 2
2 2
1 2 3
1 3 3
2 4 1
3 4 3
0 0
Sample Output
4
3
Colombia'2008