시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB181534630.667%

문제

이 밤 그날의 반딧불을

당신의 창 가까이 보낼게요

사랑한다는 말이에요

- 아이유, 밤편지 中

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

선린마을은 $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$

예제 입력 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

예제 출력 1

200
-1

$C = 3$일 때,  1번 정점에서 4번 정점으로 가는 경로 중 3번 정점을 지나는 경로는 반딧불이 3번 정점에서 8방울의 이슬을 마시고 잠들어버리기 때문에 불가능하다. 따라서 가능한 경로는 2번 정점을 거치는 경로뿐이다.

1번 정점에서 4번 정점으로 가려면 2번 혹은 3번 정점을 반드시 거쳐야 하므로, $C = 2$일 때는 4번 정점에서 1번 정점으로 갈 수 없다.