Night Letter

In Seonrin Village, there is a tradition of sending fireflies to someone dear every night.

Seonrin Village consists of $N$ houses numbered $1$ to $N$ and bidirectional roads connecting pairs of houses. A firefly may pass through other houses when there is no road directly connecting its starting house and destination, or when a more efficient route exists. House $X$ holds $2^{X}$ drops of dew, and a firefly must drink all the dew of every house it passes through during its journey, excluding the starting house and the destination. Unfortunately, each firefly has a constant $C$, and if it drinks $2^{C}$ drops of dew or more, it stops flying and falls asleep.

Chanwoo, a resident of Seonrin Village, wondered $Q$ times about the minimum time for a firefly that cannot drink $2^{C}$ drops of dew or more to travel from house $s$ to house $e$.

Write a program that answers Chanwoo's questions.

The first line gives the number of houses $N$ and the number of questions $Q$.

Starting from the second line, $N$ lines give the road information. Let $D_{i,j}$ be the $j$-th number on the $i$-th line. If $D_{i,j}$ is a positive integer, it is the time to pass through the road connecting house $i$ and house $j$; if it is $0$, there is no road connecting house $i$ and house $j$.

Starting from the next line, $Q$ lines give integers $C$, $s$, $e$ separated by spaces.

This is a question asking for the minimum time for a firefly that cannot drink $2^{C}$ drops of dew or more to travel from house $s$ to house $e$.

Print the answers to the questions over $Q$ lines, one per line, in order. If reaching the destination is impossible, print $-1$.

• $2 \leq N \leq 300$
• For all $i$, $j$ with $1 \leq i, j \leq N$: $0 \leq D_{i,j} \leq 170\,324$, $D_{i,j} = D_{j, i}$, $D_{i,i} = 0$
• $1 \leq Q \leq 500\,000$
• $1 \leq s, e \leq N$
• $1 \leq C \leq N + 1$