Last November, I wrote a problem for that was supposed to be used on this contest. Unfortunately I ended up using it in another contest that I was a problem writer for, but I'm using it here anyway. I should probably type it up again here, but I ran out of time.

If you want to solve this problem, try searching the internet for where this problem appeared before.

Meta Note: Despite this being an April Fools Contest, For this problem specifically you are not allowed to copy any complete solutions from online.

Constraints

~1 \le T \le 100~

~\color{red}{1 \le N \le 20}~

~\color{red}{M = N - 1}~

~1 \le A_i, B_i \le N~

~A_i \neq B_i~

~1 \leq P_i \leq 10^{12}~

Sample Input

1
5 4
4 10 2 3 4
1 2
2 3
2 4
1 5

Sample Output

Case #1: 19