시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB222100.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 "-1".

예제 입력 1

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

예제 출력 1

111
1
11
-1