F. Time Well Spent
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob have been close ever since high school. Now they both study at Martian University (MU), but in different departments located far apart. Their schedules are packed, and their classes take place in buildings scattered across the campus. Even though they want to spend time together, they can only meet during the short breaks between their classes.

The campus has $$$N$$$ buildings connected by $$$M$$$ undirected roads. Each road requires a certain amount of time to walk. Both Alice and Bob have several classes throughout the day, each class occurs at a specific building and lasts between a given start and end time. Class intervals do not overlap for each student. Since days on Mars do not follow Earth's fixed length, MU measures time on its own continuous scale, and a single day may be arbitrarily long. As a result, class start and end times can be large values.

Between two consecutive classes of their own, a student may roam the campus freely, traveling along any roads and visiting any buildings, as long as they arrive at their next class on time. Alice and Bob can meet only if they are in the same building at the same moment, during free periods for both. They are dedicated to their studies and will not be late to any class. They also work part time before and after their class schedules, so they will only meet between classes, never before the first class or after the last one.

Alice and Bob may choose different buildings to meet during different free intervals. Your task is to determine the maximum total time they can spend together during the day.

Input

The first line contains one integer $$$t$$$ $$$(1 \le t \le 10)$$$, the number of test cases.

Each test case begins with a line containing two integers $$$N$$$ and $$$M$$$ $$$(1 \le N \le 200,\ 1 \le M \le \frac{N(N-1)}{2})$$$, where $$$N$$$ is the number of buildings and $$$M$$$ is the number of roads. Each of the next $$$M$$$ lines contains three integers $$$u, v, w$$$ $$$(1 \le u, v \le N,\ 1 \le w \le 10^5)$$$, describing a bidirectional road between buildings $$$u$$$ and $$$v$$$ with travel time $$$w$$$ minutes.

Then a line follows containing two integers $$$A$$$ and $$$B$$$, the number of classes Alice and Bob have, respectively. The next $$$A$$$ lines describe Alice's classes; each line contains three integers $$$start, end, loc$$$ $$$(1 \le start \lt end \le 10^{15},\ 1 \le loc \le N)$$$. After that, the next $$$B$$$ lines describe Bob's classes in the same format.

The sum of $$$A + B$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer — the maximum total time Alice and Bob can spend together.

Example
Input
1
4 5
1 2 3
1 3 4
2 3 2
3 4 1
2 4 1
2 2
1 10 1
20 30 2
1 10 1
20 30 3
Output
6