|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||0||0||0||0.000%|
There are $n$ intersections in Bytetown, connected with $m$ one-way streets. These intersections are labeled by $1,2,\dots,n$. 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, move along a street at least $k_i$ times, and finally arrive to the $t_i$-th intersection. Note that $k_i$ is the required number of moves, not streets: it is allowed to use any street more than once.
Little Q's smartphone will record 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. Please 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$) denoting 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$.
In the next line, there is an integer $q$ ($1 \leq q \leq 100\,000$) denoting 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 a line containing a single integer: the minimum total walking length. If there is no solution, please print "
2 3 3 1 2 1 2 3 10 3 1 100 3 1 1 1 1 2 1 1 3 1 2 1 1 2 1 1 2 1 1
111 1 11 -1