Crazy Circuits

You have just built a circuit board for your new robot, and now you need to power it. Your robot circuit consists of a number of electrical components, each of which requires a certain amount of current to operate. Every component has a + lead and a - lead, which are connected to each other at junctions on the circuit board. Current flows through a component from + to - (but note that a component does not "use up" the current: everything that comes in through the + end goes out through the - end).

The junctions on the board are labeled $1, \dots, N$, plus two special junctions labeled + and - where the power supply terminals are connected. The + terminal connects only + leads, and the - terminal connects only - leads. At every junction, all the current that enters from the - leads of the connected components leaves through the connected + leads, and you are able to control how much current flows to each connected + lead (the methods for doing so are beyond the scope of this problem). Moreover, you have assembled the circuit so that there are no feedback loops (components chained in a way that would let current flow around a loop).

Figure 1: Two examples of valid circuit diagrams. In (a), every component can be powered along a directed path from the positive terminal to the negative terminal. In (b), components 4 and 6 cannot be powered, because there is no directed path from junction 4 to the negative terminal.

To save power, and also to keep your circuit from overheating, you would like to use as little current as possible to make your robot work. What is the smallest amount of current you need to send through the + terminal (all of which you may imagine necessarily leaving through the - terminal) so that every component on your robot receives its required supply of current?

The input contains multiple test cases. Each test case begins with a single line containing two integers $N$ ($0 \le N \le 50$), the number of junctions not counting the positive and negative terminals, and $M$ ($1 \le M \le 200$), the number of components in the circuit diagram. Each of the next $M$ lines describes one component. The $i$-th component description contains three fields: $p_i$, the positive junction the component is connected to; $n_i$, the negative junction the component is connected to; and an integer $I_i$ ($1 \le I_i \le 100$), the minimum amount of current component $i$ needs to function. Each of $p_i$ and $n_i$ is given either as the character + (the positive terminal), the character - (the negative terminal), or an integer between $1$ and $N$ (one of the numbered junctions). No two components share the same positive junction and the same negative junction at once. The end of input is marked by an invalid test case with $N = M = 0$, which should not be processed.

For each test case, print a single integer: the minimum amount of current that must be supplied at the positive terminal so that every component is powered. If there is no way to direct a sufficient amount of current to every component simultaneously, print impossible instead.