나무평평설

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

찬우는 이를 증명하기 위해, 포스텍에서 $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$이 되도록 하는 연산의 최소 횟수를 출력한다.