There are $n$ intersections in Bytetown, connected with $m$ one way streets. Little Q likes sport walking very much, he plans to walk for $q$ days. On the $i$-th day, Little Q plans to start walking at the $s_i$-th intersection, walk through at least $k_i$ streets and finally return to the $t_i$-th intersection.
Little Q's smart phone will record his walking route. Compared to stay healthy, Little Q cares the statistics more. So he wants to minimize the total walking length of each day. Please write a program to help him find the best route.

The first line of the input contains an integer $T(1\leq T\leq10)$, denoting the number of test cases.
In each test case, there are $2$ integers $n,m(2\leq n\leq 50,1\leq m\leq 10000)$ in the first line, denoting the number of intersections and one way streets.
In the next $m$ lines, each line contains $3$ integers $u_i,v_i,w_i(1\leq u_i,v_i\leq n,u_i\neq v_i,1\leq w_i\leq 10000)$, denoting a one way street from the intersection $u_i$ to $v_i$, and the length of it is $w_i$.
Then in the next line, there is an integer $q(1\leq q\leq 100000)$, denoting the number of days.
In the next $q$ lines, each line contains $3$ integers $s_i,t_i,k_i(1\leq s_i,t_i\leq n,1\leq k_i\leq 10000)$, describing the walking plan.

For each walking plan, print a single line containing an integer, denoting the minimum total walking length. If there is no solution, please print -1.