Bones's Battery

Bones is shopping for an electric shuttle for the school district where his mother works. Every school has a charging station. Call the range of the shuttle the greatest distance it can drive on a full charge.

A trip from any school to any other school has to finish with at most $K$ rechargings. The shuttle's battery starts out empty, so it must be charged before it sets off, and that charge counts toward the $K$. It may be charged again at any school it stops at along the way.

At most one road runs between any pair of schools, and every pair of schools is joined by some sequence of roads. Given the road network and $K$, find the smallest range the electric shuttle needs.

The first line has one integer $T$ ($1 \le T \le 50$), the number of test cases.

Each test case begins with a line of three integers $N$, $K$, and $M$ ($2 \le N \le 100$, $1 \le K \le 100$), where $N$ is the number of schools, $K$ is the largest number of rechargings allowed on one trip, and $M$ is the number of roads.

Each of the next $M$ lines has three integers $u_i$, $v_i$, and $d_i$ ($0 \le u_i, v_i < N$, $u_i \ne v_i$, $1 \le d_i \le 10^9$). Road $i$ joins school $u_i$ and school $v_i$ in both directions and has length $d_i$. Schools are numbered from 0.

For each test case, print the smallest required range on one line.