20610번 - Walking Plan 다국어

문제

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".

제한

힌트