Problem D
NTNU Orienteering

After the unification of NTNU and HiNT, the now all-powerful NTNU has a lot of campuses at its disposal. You, a student of Computer Science, are facing the problem of having to attend lectures at several campuses; campuses that are far away from each other.

You’re given a handy time schedule with all your lectures listed for a given day, and, using the map app on your phone, you write down the time it takes on the bus between each campus. You notice that it won’t always be possible to attend every lecture due to overlapping lectures and travel times between campuses. Luckily, you have an “AtB GOLD CARD” that grants you unlimited bus travel at no cost.

Given the lecture time schedules for a day and the bus travel times between each campus, what is the highest number of lectures that you can attend from start to finish for a given day? You may choose to start your day at any campus (you are an extremely early riser).

Input

The first line of the input consists of a single integer $T$, the number of test cases.
The first line of each test case is an integer, $C$, denoting the number of campuses.
The second line contains another integer, $L$, denoting the number of lectures you have this day.

This is followed by $\frac{1}{2} \times C \times (C-1)$ (combinations of campuses) lines, each containing 3 integers $i$ $j$ $t_{i, j}$ separated by spaces, where $t_{i, j}$ describes the time the bus route between campus $i$ and campus $j$ takes in microseconds. Campus ids start at index $0$ and end at index $C-1$. Each pair of campuses will be listed exactly once, and you can assume that the same bus goes both ways, so that the time on the bus from $i$ to $j$ is equal to the time on the bus from $j$ to $i$. Traveling between lecture rooms within the same campus takes no time.

Then follows $L$ lines of lecture durations for this day. Each line contains 3 integers $C_ l$ $S_ l$ $E_ l$, where $C_ L$ gives the index of the campus the lecture is held at, $S_ l$ is the absolute start time of the lecture in microseconds and $E_ l$ is the end time of the lecture in microseconds. You can start traveling to the next lecture the same microsecond as the lecture ends.

• $1 \leq T \leq 20$

• $1 \leq C \leq 200$

• $1 \leq L \leq 1000$

• $1 \leq t_{i,j} \leq 8\, 600\, 000$

• $0 \leq C_ l < C$

• $0 \leq S_ l < E_ l \leq 8\, 600\, 000$

Output

Output the highest number of lectures that it is possible to attend completely.

1
3
2
0 1 5
1 2 5
0 2 100
0 0 90
2 100 110

2