PEG Judge - WC99 - S

Woburn Challenge 1999 - Suicidal

Star Wars Episode III: The Phantom Lucas

The Star Wars franchise has been so secretive about the plot of the next 2 movies that even their most die-hard fans have been fooled into thinking that Darth Vader uses the Force to track down the Jedi Knights. However, what they don't realize is that Star Wars is really an autobiography of George Lucas. If you don't want to know the plot of the movie, skip to the next problem because some shocking details will be revealed. First, George Lucas is really the Emperor of the Dark Side. Second, he will actually use his acquired wealth (from the first 4 movies) to bribe weak-minded Jedi into revealing information leading to the capture of other Jedi. Lastly, being a greedy impresario, he obviously wants to minimize the total amount of bribes he hands out. So here is the situation he faces:

1) There are n Jedi, each with knowledge that will reveal the location of 0 or more other Jedi.

2) Some of these Jedi can be bribed into revealing the location of others. The Jedi are a little greedy and so each one has a price list that he will use to determine the price of bribery, i.e. each Jedi he can compromise has a price and for that price, only that one Jedi will be compromised. Say that Jedi X knows the location of 2 Jedi A and B. He will give up Jedi A for $10 and B for $15. If you bribe him with $15, he will only give up B. If you then want to reveal A, you have to bribe him again with $10 to reveal A.

3) If you find out the location of a Jedi (by bribing somebody else), you can then use the persuasion powers of the Force to make the captured Jedi reveal everybody he knows about - obviously, these revelations will come at no cost.

Somehow, you have acquired a list of all Jedi and the prices they charge. You want to come up with a bribery plan such that all Jedi can be captured at a minimum cost. If all the Jedi can be caught, output the minimum bribe required. However, if all the Jedi cannot be caught, output "IMPOSSIBLE". Note that bribing a Jedi doesn't mean that he has been captured. Note that there will be at most 100 spies and at most 1000 possible briberies to do.

Input

Line 1: # of input sets
The next lines will contain each input set.
Each input set will terminate with a 0 0 0.
1st line of input set: # of spies.
Next few lines: X Y n (means that X can be bribed for $n to reveal Y)