# Problem C

Circuit Game

You’ve just found a most curious electro-mechanical game in a dusty corner of the saloon. No one seems to know where it came from, but the instructions promise riches to those who are able to play it well.

The operation of the machine is as follows. First, you
insert some coins into the machine. Then, you flip some of the
switches on the front of the machine. Each switch is initially
in the ON position, and to switch it to the OFF position, you
must pay a price. The total cost of all switches you put in the
OFF position must be at most the value of the coins you
inserted. When you’re happy with your selection of switches,
you hit the big red button. Then, the game runs a series of
test cases against your selection of switches. Each time you
pass a test, you will receive the reward amount associated with
that test. However, **as soon as you fail even a
single test, the game halts and does not process any further
tests**. You would like to maximize the amount of profit you
make from a single round of the game, given that you can spend
at most C coins.

Internally, the machine works as follows. There are
$N$ terminals, numbered 1
through $N$, and a battery
which spans terminals 1 and 2. Terminals may be joined by
switches, each of which connects (in the ON position) or
doesn’t connect (in the OFF position) two distinct terminals.
We say that there is *power* across two terminals
$a$ and $b$ if there is a path between
$a$ and $1$ and a path between $b$ and $2$ (or between $a$ and $2$ and between $b$ and $1$). Note that such a path can only
go through switches which are in the ON position. You will pass
a test case if there is **not** any power across
the two terminals associated with the test.

By the way, you should ensure that the battery is not short-circuited (i.e., there should not be a path from terminal 1 to 2), or else the entire machine will probably explode, taking you and your rewards with it.

## Input

The first line contains 4 integers, $C$, $N$, $M$, and $T$, where $2\le N$, $1\le C, M, T$ and $C, N, M, T\le 1000$. The next $M$ lines each contain 3 integers $u$, $v$, and $c$, indicating that there is a switch between terminals $u$ and $v$ with cost $c$ ($1\le u<v\le N$, $0\le c\le 1000$). The next $T$ lines each contain 3 integers $u$, $v$, and $r$, indicating that there is a test case which tests terminals $u$ and $v$ with a reward of $r$ ($1\le u<v\le N$, $0\le r\le 1000$). There is at most one switch and one test case for a given pair of terminals.

## Output

Output the largest possible profit you can obtain, i.e., the
total reward minus the total number of coins you used, for a
single play of the game. If there is no way to prevent a short
circuit or no way to make positive amount of profit, output
“`The only winning move is not to
play.`”

Sample Input 1 | Sample Output 1 |
---|---|

3 4 3 2 2 4 2 1 3 3 3 4 1 2 3 10 1 4 100 |
7 |

Sample Input 2 | Sample Output 2 |
---|---|

20 5 5 3 4 5 4 3 4 9 1 5 8 1 3 4 2 3 3 2 4 3 3 5 8 4 5 7 |
6 |

Sample Input 3 | Sample Output 3 |
---|---|

1 3 2 1 1 2 1 2 3 0 1 3 1 |
The only winning move is not to play. |