Graph Path with Edge Weight Halving

You are given an undirected/directed (depending on the input) graph \( G \) with \( n \) nodes. The graph is provided in the form of an adjacency matrix \( A \) where \( A_{i,j} = 0 \) indicates that there is no edge from node \( i \) to node \( j \) and \( A_{i,j} > 0 \) means there is an edge from \( i \) to \( j \) with weight \( A_{i,j} \).

You will be given \( m \) queries. In each query, you are asked to find the minimum possible total weight of a path from node \( a \) to node \( b \) that uses exactly \( c \) edges. In addition, you are allowed to choose exactly one edge on the path and replace its weight with \( \left\lfloor \frac{w}{2} \right\rfloor \) (if the same edge is used more than once in the path, the weight halving applies to only one occurrence; the rest use the original weight).

If there exists no path satisfying the conditions, output \(-1\).

inputFormat

The first line contains an integer \( n \) representing the number of nodes.

Then follow \( n \) lines, each containing \( n \) integers. The \( j\text{-th} \) integer in the \( i\text{-th} \) line is \( A_{i,j} \), the weight of the edge from node \( i \) to node \( j \) (or \( 0 \) if no edge exists).

The next line contains an integer \( m \) representing the number of queries.

Each of the following \( m \) lines contains three integers \( a, b, c \) where \( a \) and \( b \) are the start and end nodes (1-indexed) and \( c \) is the exact number of edges the path must use.

outputFormat

For each query, output the minimum total weight of a path that uses exactly \( c \) edges from node \( a \) to node \( b \) with the possibility of halving one edge weight as described. If no such path exists, output \(-1\).

sample

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

2
4