## Another Contest 2 Problem 1 - Poutine

View as PDF

Points: 15
Time limit: 0.6s
Memory limit: 256M

Problem types

Fast Fingers Thomas is delivering poutine to Wilson's restaurants!

Fast Fingers Thomas will drive a truck on a directed, weighted graph with vertices. The weight of each edge in the graph is the length of the edge. He has trips he needs to make.

Each trip has three parameters, a source vertex , a destination vertex , and a number of days . Thomas has days to travel from vertex to vertex . In a given day, Thomas starts at a vertex and traverses a nonnegative number of edges, ending the day at some vertex (possibly the same one). Define to be the smallest value such that, in a single day, the sum of the weights of the edges that Thomas drives on does not exceed , and subject to this, Thomas can get from to in days. In the event that it's impossible to do this, Thomas does no driving and is zero.

#### Constraints

All queries are pairwise distinct.

#### Input Specification

The first line contains a single positive integer, .

The next lines contain space-separated non-negative integers. The th integer in the th line of this section, , indicates the length of the directed edge connecting vertex to vertex , or if no such edge exists. It is guaranteed there are no self-loops.

The next line contains a single positive integer, .

The next lines each contain three space-separated positive integers, , , and , representing a query for .

#### Output Specification

Output lines. On the th line, output the answer to the th query.

#### Sample Input

3
0 1 2
1 0 1
2 1 0
2
1 3 1
1 3 2

#### Sample Output

2
1