Woburn Challenge 1999 - Suicidal

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 Specification

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

Output Specification

For each test case, output the cheapest price for which all the Jedi can be caught, and IMPOSSIBLE if it can not be done.

Sample Input

1
4
1 2 1
2 3 1
3 4 1
4 1 1
0 0 0

Sample Output

1