이 밤 그날의 반딧불을 </p>

당신의 창 가까이 보낼게요

사랑한다는 말이에요

- 아이유, 밤편지 中

</blockquote>

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

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

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

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

입력 형식

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

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

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

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

출력 형식

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

예제 입력

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

예제 출력

200
-1