31777번 - 나무평평설

문제

지구평면설로부터 큰 호응을 받은 찬우는, 이번에는 나무평평설을 주장하기 시작했다!

찬우는 이를 증명하기 위해, 포스텍에서 $N$개의 정점과 $N-1$개의 가중치를 갖는 간선으로 이루어진 무향 트리를 준비했다. 이 트리의 각 정점에는 1ドル$번부터 $N$번까지 번호가 붙어 있다. 찬우는 다음의 연산들을 원하는 만큼 적용해 모든 간선의 가중치를 0ドル$으로 만들려고 한다.

• 임의의 두 정점 번호 $u,ドル $v$를 고르고, $u$번 정점과 $v$번 정점을 양 끝점으로 하는 단순 경로의 모든 간선의 가중치를 1ドル$ 감소시킨다.

이때의 연산에 의해 가중치가 0ドル$보다 작아질 수 있음을 유의하라.

하지만 찬우는 여전히 게으름뱅이라 적용해야 하는 연산의 횟수를 가능한 한 적게 하고 싶다. 찬우가 모든 간선의 가중치를 0ドル$으로 만들기 위한 연산의 최소 횟수를 구해주자!

입력

첫 번째 줄에 테스트케이스의 개수 $T$가 주어진다. (1ドル \leq T \leq 10,000円$)

각 테스트케이스의 첫 번째 줄에 트리의 정점의 개수 $N$이 주어진다. (2ドル \leq N \leq 300,000円$)

각 테스트케이스의 두 번째 줄부터 $N-1$개의 줄에 걸쳐, 각 줄마다 $i$번째 트리의 간선의 양 끝의 정점의 번호 $u_i, v_i$와 간선의 초기 가중치 $w_i$가 각각 공백으로 구분되어 주어진다. (1ドル \leq u_i < v_i \leq N;$ 0ドル < w_i \leq 10^9$)

주어지는 수는 모두 정수이며, 모든 테스트케이스에 대해 $N$의 합이 300ドル,000円$ 이하임이 보장된다.

출력

각 테스트케이스에 대해 모든 간선의 가중치가 0ドル$이 되도록 하는 연산의 최소 횟수를 출력한다.

제한

힌트