인하니카 공화국

인하니카 공화국은 1번부터 $N$번까지 번호가 붙은 $N$개의 섬으로 이루어진 나라다. 예전에는 섬 사이를 오가기가 매우 어려웠지만, 다리 설계자 '진'이 두 섬을 잇는 다리를 최소 개수만 놓아 모든 섬을 서로 오갈 수 있게 만들었다. 그래서 다리는 $N - 1$개이고, 섬과 다리는 하나의 트리를 이룬다.

1번 섬에 사는 진은 어느 날 위험한 소문을 들었다. 1번 섬을 뺀 나머지 섬 중에서 다리가 하나뿐인 어느 섬에 연쇄 살인마 괴도 '루팡'이 숨어 자기 목숨을 노린다는 소문이었다. 루팡이 정확히 어느 섬에 있는지는 알 수 없으니, 진은 1번 섬이 아니면서 다리가 하나뿐인 모든 섬에서 1번 섬으로 가는 경로를 남김없이 끊으려 한다.

다리를 폭파하려면 다이너마이트가 필요하고, 필요한 개수는 다리 크기에 따라 다리마다 다르다. 다이너마이트는 매우 비싸서 진은 쓰는 개수를 최소로 줄이고 싶다. 각 다리를 폭파하는 데 드는 다이너마이트 개수가 주어질 때, 필요한 최소 다이너마이트 개수를 구하라.

위 그림처럼 섬과 다리별 다이너마이트 개수가 주어진 경우, 빨간색으로 표시한 다리를 폭파하면 다이너마이트를 가장 적게 쓰면서 루팡의 접근을 막을 수 있다.

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

각 테스트 케이스의 첫 줄에는 섬의 수 $N$ ($1 \le N \le 1000$)과 다리의 수 $M$이 주어진다. 다리는 모든 섬을 잇는 최소 개수이므로 $M = N - 1$이다.

이어지는 $M$개의 줄에는 그 다리가 잇는 두 섬의 번호와, 그 다리를 폭파하는 데 필요한 다이너마이트의 개수 $D$ ($1 \le D \le 20$)가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 필요한 최소 다이너마이트 개수를 한 줄에 출력한다. $N = 1$이면 폭파할 다리가 없으므로 0을 출력한다.