가중치가 증가하는 최단 경로

"인생은 이야기를 지어낼 만큼 길지 않다"라고 Ahmed Aly가 말했다. 그래서 이 문제도 곧바로 본론으로 들어간다.

정점이 $N$개인 가중치 방향 그래프가 주어진다. 정점 번호는 $1$번부터 $N$번까지이고, 간선의 가중치는 모두 양의 정수이며 서로 다르다.

쿼리는 세 정수 $A$, $B$, $C$로 주어진다. 정점 $A$에서 출발해 정점 $B$에서 끝나고, 간선을 $C$개 이하로 쓰며, 지나는 간선의 가중치가 진행 방향으로 갈수록 커지는 경로를 생각한다. 즉 각 간선의 가중치는 바로 앞에 지난 간선의 가중치보다 커야 한다. 경로의 첫 간선에는 이 조건이 붙지 않는다.

쿼리마다 이런 경로의 간선 가중치 합 중 가장 작은 값을 구한다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다 ($1 \le T \le 100$).

각 테스트 케이스의 첫째 줄에는 정점의 수 $N$, 간선의 수 $M$, 쿼리의 수 $Q$가 공백 하나로 구분되어 주어진다 ($2 \le N \le 150$, $0 \le M \le 3000$, $1 \le Q \le 1000$).

이어지는 $M$개 줄에는 각각 세 정수 $X$, $Y$, $Z$가 공백 하나로 구분되어 주어진다 ($1 \le X, Y \le N$, $1 \le Z \le 3000$, $X \ne Y$). 정점 $X$에서 정점 $Y$로 가는 가중치 $Z$의 간선을 뜻한다. 같은 두 정점을 잇는 간선이 여러 개 있을 수도 있다.

이어지는 $Q$개 줄에는 각각 세 정수 $A$, $B$, $C$가 공백 하나로 구분되어 주어진다 ($1 \le A, B \le N$, $0 \le C \le M$, $A \ne B$). 위에서 설명한 쿼리 하나를 뜻한다.

각 쿼리마다 조건을 만족하는 경로의 최소 가중치 합을 한 줄에 출력한다. 조건을 만족하는 경로가 없으면 $-1$을 출력한다. 테스트 케이스 사이에 빈 줄을 넣지 않는다.