본즈의 배터리

본즈는 어머니가 일하는 교육청에 들일 전기 셔틀버스를 알아보고 있다. 학교마다 충전소가 하나씩 있다. 완전히 충전한 셔틀버스가 달릴 수 있는 최대 거리를 주행 거리라고 하자.

어떤 학교에서 다른 어떤 학교로 가더라도 충전 횟수가 $K$번을 넘지 않아야 한다. 셔틀버스의 배터리는 처음에 비어 있어서 길을 나서기 전에 반드시 한 번 충전해야 하고, 이 충전도 $K$번에 포함된다. 가는 길에 들르는 학교에서는 다시 충전해도 된다.

두 학교를 잇는 도로는 많아야 하나이고, 어느 두 학교 사이에도 도로를 따라가는 경로가 있다. 도로망과 $K$가 주어질 때, 전기 셔틀버스에 필요한 최소 주행 거리를 구하라.

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 50$)가 주어진다.

각 테스트 케이스의 첫 줄에는 세 정수 $N$, $K$, $M$ ($2 \le N \le 100$, $1 \le K \le 100$)이 주어진다. $N$은 학교의 수, $K$는 한 번의 이동에서 허용되는 최대 충전 횟수, $M$은 도로의 수다.

다음 $M$개의 줄에는 각각 세 정수 $u_i$, $v_i$, $d_i$ ($0 \le u_i, v_i < N$, $u_i \ne v_i$, $1 \le d_i \le 10^9$)가 주어진다. $i$번 도로는 학교 $u_i$와 학교 $v_i$를 양방향으로 잇고, 길이는 $d_i$다. 학교 번호는 0부터 시작한다.

각 테스트 케이스마다 필요한 최소 주행 거리를 한 줄에 출력한다.