연결

바이트오시아(Byteotia) 기반시설부는 도시들 사이를 잇는 경로의 길이를 빠르게 알려 주는 프로그램을 만들려고 한다. 보통은 가장 짧은 경로를 찾지만, 여기서는 $k$번째로 짧은 경로를 찾는다. 경로에는 순환이 있을 수 있으므로 같은 도시를 여러 번 지날 수도 있다.

예를 들어 두 도시를 잇는 경로가 네 개 있고 그 길이가 각각 $2$, $4$, $4$, $5$라면, 가장 짧은 경로의 길이는 $2$, 두 번째로 짧은 경로의 길이는 $4$, 세 번째는 $4$, 네 번째는 $5$이다. 길이가 같은 경로도 각각 따로 센다.

경로는 항상 도로를 하나 이상 지나므로, 출발 도시와 도착 도시가 같은 경로는 반드시 순환을 이루어야 한다.

다음을 수행하는 프로그램을 작성하라.

• 표준 입력에서 바이트오시아의 도로망과 경로 길이에 대한 질의들을 읽는다.
• 각 질의의 답을 계산하여 표준 출력에 쓴다.

첫째 줄에 공백으로 구분된 두 정수 $n$과 $m$이 주어진다. $1 \le n \le 100$이고 $0 \le m \le n^2 - n$이다. 각각 도시의 수와 도로의 수이다. 도시는 $1$번부터 $n$번까지 번호가 매겨져 있다.

이어지는 $m$개의 줄에는 공백으로 구분된 세 정수 $a$, $b$, $l$이 주어진다. $a \ne b$이고 $1 \le l \le 500$이다. 각 줄은 도시 $a$에서 도시 $b$로 가는 길이 $l$짜리 일방통행 도로 하나를 나타낸다. 임의의 순서쌍인 두 도시 사이에 그 방향으로 가는 도로는 최대 하나만 있다.

그다음 줄에는 질의의 수를 나타내는 정수 $q$가 주어지며 $1 \le q \le 10000$이다. 이어지는 $q$개의 줄에는 각각 공백으로 구분된 세 정수 $c$, $d$, $k$가 주어지며 $1 \le k \le 100$이다. 각 질의는 도시 $c$에서 도시 $d$로 가는 $k$번째로 짧은 경로의 길이를 묻는다.

질의가 주어진 순서대로 각 질의의 답을 한 줄에 하나씩 출력한다. $i$번째 질의에 대해서는 구하는 경로의 길이를 정수 하나로 출력하고, 그러한 경로가 $k$개보다 적으면 $-1$을 출력한다.