Bonnie's Battery#6962
Bonnie is studying what battery capacity would be most suitable for the school buses in the district where his mother works. Each school has its own charging station. Any trip from one school to another must be completed with no more than recharges. The battery is initially empty and must be fully charged before the start of each trip; this initial charge also counts toward the recharges.
Between each pair of schools, there is at most one road, and the road network is connected, meaning there is always at least one path between any two schools. Traveling one unit of distance requires one unit of charge.
Given the road network and the value of , determine the minimum necessary battery capacity for the school buses.
The first line contains the number of test cases t~(1 \le t \leq 50).
Each test case begins with a line containing three integers , , and m~(2 \le n \le 100, 1 \le k \le 100), where:
— the number of schools,
— the maximum allowed number of recharges during a trip,
— the number of roads.
Then follow lines, each containing 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).
These data describe that road connects schools u_i and v_i (schools are numbered from zero) with a bidirectional path of length d_i.
For each test case, print on a separate line the minimum required battery capacity.
Example 1