나무평평설

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

찬우는 이를 증명하려고 포스텍에서 가중치가 있는 간선 $N-1$개로 이어진 무향 트리를 준비했다. $N$개의 정점에는 $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$으로 만드는 연산의 최소 횟수를 출력한다.