벤자민 고무나무

뒷마당에 벤자민 고무나무가 한 그루 있다. 이 나무의 뿌리는 집 밑을 파고들지 않고 마당의 빈 공간으로만 뻗어서, 친구들은 이 나무를 착한 벤자민이라고 부른다. 새로 집을 짓는 친구가 같은 나무를 갖고 싶어 해서, 뿌리 일부를 잘라 나눠 주기로 했다.

나무의 뿌리는 $N$개이고 $1$번부터 $N$번까지 번호가 붙어 있다. 서로 다른 두 뿌리를 잇는 연결이 $M$개 있고, 뿌리 $a$와 $b$를 잇는 연결을 끊는 데는 힘 $w$가 든다.

뿌리 전체를 비어 있지 않은 두 무리로 나누려고 한다. 두 무리 사이를 잇는 연결은 하나도 남으면 안 되고, 드는 힘은 끊은 연결의 힘을 모두 더한 값이다. 필요한 힘의 최솟값을 구하라.

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

각 테스트 케이스의 첫 줄에는 뿌리의 개수 $N$과 연결의 개수 $M$이 주어진다 ($2 \le N \le 500$, $N-1 \le M \le N(N-1)/2$).

다음 $M$개 줄에는 세 정수 $a_i$, $b_i$, $w_i$가 주어진다 ($1 \le a_i, b_i \le N$, $a_i \ne b_i$, $1 \le w_i \le 1000$). 뿌리 $a_i$와 $b_i$가 연결되어 있고, 그 연결을 끊는 데 힘 $w_i$가 든다는 뜻이다.

두 뿌리를 잇는 연결은 많아야 하나이고, 모든 뿌리는 연결을 따라가면 서로 이어진다.

각 테스트 케이스마다 필요한 힘의 최솟값을 한 줄에 하나씩 출력한다.

첫 번째 예제에서 뿌리 $1$만 떼어 내면 $2+3+5=10$의 힘이 든다. 대신 $\{1,2\}$와 $\{3,4\}$로 나누면 $3+5+5+5=18$의 힘이 든다.