Connections

The Byteotian Ministry of Infrastructure wants a program that quickly reports the lengths of routes between towns. People usually look for the shortest route, but here they want the $k$-th shortest route. Routes may contain cycles, so a town can be visited more than once.

For example, if there are four routes between two towns with lengths $2$, $4$, $4$, and $5$, then the shortest route has length $2$, the second shortest has length $4$, the third has length $4$, and the fourth has length $5$. Routes of equal length are counted separately.

A route always uses at least one road, so a route that starts and ends at the same town must follow a cycle.

Write a program that:

• reads a description of the Byteotian road network and a list of route-length queries from standard input,
• computes the answer to each query and writes it to standard output.

The first line contains two integers $n$ and $m$ separated by a single space, where $1 \le n \le 100$ and $0 \le m \le n^2 - n$. They are the number of towns and the number of roads. Towns are numbered from $1$ to $n$.

Each of the next $m$ lines contains three integers $a$, $b$, and $l$ separated by single spaces, where $a \ne b$ and $1 \le l \le 500$. Each line describes a one-way road of length $l$ that leads from town $a$ to town $b$. For any ordered pair of towns there is at most one road in that direction.

The next line contains one integer $q$, where $1 \le q \le 10000$, the number of queries. Each of the following $q$ lines contains three integers $c$, $d$, and $k$ separated by single spaces, where $1 \le k \le 100$. Each query asks for the length of the $k$-th shortest route from town $c$ to town $d$.

Write the answers to the queries, one per line, in the order the queries are given. For the $i$-th query, print a single integer: the length of the requested route, or $-1$ if fewer than $k$ such routes exist.