Walking Plan

There are $n$ intersections in Bytetown, connected by $m$ one-way streets. The intersections are labeled $1,2,\dots,n$. Little Q likes sport walking very much, and he plans to walk for $q$ days. On the $i$-th day, Little Q plans to start walking at the $s_i$-th intersection, move along a street at least $k_i$ times, and finally arrive at the $t_i$-th intersection. Here $k_i$ is the required number of moves, not streets: the same street may be used more than once.

Little Q's smartphone records his walking route. Little Q cares more about statistics than about staying healthy. So he wants to minimize the total walking length on each day. Write a program to help him find the best route.

The first line contains a single integer $T$ ($1 \leq T \leq 10$), the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($2 \leq n \leq 50$, $1 \leq m \leq 10\,000$), the number of intersections and one-way streets.

Each of the next $m$ lines contains three 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 10\,000$), denoting a one-way street from intersection $u_i$ to intersection $v_i$ with length $w_i$.

The next line contains an integer $q$ ($1 \leq q \leq 100\,000$), the number of days.

Each of the next $q$ lines contains three integers $s_i$, $t_i$, $k_i$ ($1 \leq s_i, t_i \leq n$, $1 \leq k_i \leq 10\,000$), describing the walking plan.

For each walking plan, print one line containing a single integer: the minimum total walking length. If there is no solution, print "-1".