밤편지

선린마을에는 밤마다 소중한 사람을 향해 반딧불을 보내는 전통이 있다.

선린마을은 $1$번부터 $N$번까지의 번호가 붙은 $N$채의 집과 집 사이를 잇는 양방향 도로로 이루어져 있다. 반딧불은 출발지와 도착지를 직접 연결하는 길이 없거나 더 효율적인 경로가 있는 경우 다른 집들을 거쳐갈 수 있다. $X$번 집에는 $2^{X}$ 방울의 이슬이 있으며, 반딧불은 출발지와 도착지를 제외하고 이동하는 동안 거치는 모든 집의 이슬을 반드시 모두 마셔야 한다. 안타깝게도 반딧불은 각각 상수 $C$를 가지고 있으며, 이슬을 $2^{C}$ 방울 이상 마시면 더 이상 날아가지 않고 잠들어 버린다.

선린마을의 주민 찬우는 이슬을 $2^{C}$ 방울 이상 마실 수 없는 반딧불이 $s$번 집에서 $e$번 집으로 이동하는 데 걸리는 최소 시간이 $Q$번이나 궁금해졌다.

찬우의 질문에 답하는 프로그램을 작성하자.

첫째 줄에 집의 수 $N$과 질문의 수 $Q$가 주어진다.

둘째 줄부터 $N$줄에 걸쳐 길의 정보가 주어진다. $i$번 줄의 $j$번째 수를 $D_{i,j}$라고 할 때, $D_{i,j}$가 양의 정수라면 $i$번 집과 $j$번 집을 잇는 길을 통과하는 시간을 의미하고, $0$이라면 $i$번 집과 $j$번 집 사이를 연결하는 길이 없다는 의미이다.

다음 줄부터는 $Q$개의 줄에 걸쳐 정수 $C$, $s$, $e$가 공백으로 구분되어 주어진다.

이는 이슬을 $2^{C}$ 방울 이상 마실 수 없는 반딧불이 $s$번 집에서 $e$번 집으로 이동하는 데 걸리는 최소 시간을 묻는 질문이다.

$Q$개의 줄에 걸쳐 질문의 답을 한 줄에 하나씩 순서대로 출력한다. 목적지에 도착하는 것이 불가능한 경우에는 $-1$을 출력한다.

• $2 \leq N \leq 300$
• $1 \leq i, j \leq N$인 모든 $i$, $j$에 대해 $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$