산책 계획

바이트타운에는 $n$개의 교차로가 있고, $m$개의 일방통행 도로가 이들을 잇는다. 교차로에는 $1,2,\dots,n$의 번호가 붙어 있다. 리틀 Q는 스포츠 산책을 아주 좋아해서 $q$일 동안 산책할 계획을 세웠다. $i$번째 날에 리틀 Q는 $s_i$번 교차로에서 출발하여 도로를 따라 적어도 $k_i$번 이동한 뒤 마지막으로 $t_i$번 교차로에 도착하려 한다. 여기서 $k_i$는 필요한 이동 횟수이지 도로 개수가 아니다. 같은 도로를 여러 번 이용해도 된다.

리틀 Q의 스마트폰은 산책 경로를 기록한다. 리틀 Q는 건강보다 통계에 더 관심이 많다. 그래서 그는 매일 산책한 총 길이를 최소화하려 한다. 그의 최적 경로를 찾는 프로그램을 작성하시오.

첫째 줄에는 테스트 케이스의 수 $T$가 주어진다. ($1 \leq T \leq 10$) 각 테스트 케이스는 다음과 같다.

첫째 줄에는 교차로의 수 $n$과 일방통행 도로의 수 $m$이 주어진다. ($2 \leq n \leq 50$, $1 \leq m \leq 10\,000$)

다음 $m$개 줄에는 각각 세 정수 $u_i$, $v_i$, $w_i$가 주어진다. 이는 $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$)

그다음 줄에는 날의 수 $q$가 주어진다. ($1 \leq q \leq 100\,000$)

다음 $q$개 줄에는 각각 세 정수 $s_i$, $t_i$, $k_i$가 주어진다. 이는 산책 계획을 나타낸다. ($1 \leq s_i, t_i \leq n$, $1 \leq k_i \leq 10\,000$)

각 산책 계획마다 산책한 총 길이의 최솟값을 한 줄에 하나씩 출력한다. 답이 없으면 "-1"을 출력한다.