보스 중의 보스

Krzysztof J.는 슈체친에서 이름난 마피아 보스다. 다음 주에 그는 부하들을 불러 모임을 열려고 한다. 편의상 부하들에게 $1, 2, \dots, n$이라는 번호를 붙이자. 이들은 초밥을 먹거나 볼링을 친 뒤 저녁 식사 자리에서 사업 이야기를 나눌 것이다. 하지만 이런 모임을 준비하는 일은 쉽지 않다. 초대된 마피아들은 성격이 불같아서 여러 주제를 두고 자주 부딪히고, 그러다 보면 싸움으로 번지기도 하기 때문이다. 그래서 Krzysztof는 당신에게 도움을 청했다.

정확히 $n - 1$쌍의 마피아가 서로 친구이며, 그러한 쌍마다 두 사람이 직접 합의에 도달하는 데 걸리는 예상 시간을 알아냈다. 또한 친구 관계로 정의되는 그래프를 만들었다. 이 그래프는 연결되어 있으므로, 친구가 아닌 두 마피아가 합의에 도달하는 예상 시간은 그래프에서 두 사람을 잇는 경로 위의 인접한 마피아들 사이에서 직접 합의에 도달하는 시간들의 합의 최솟값이다.

저녁 식사 동안 마피아들은 긴 탁자의 한쪽에 앉는다. 좌석에는 $1, 2, \dots, w+1$이라는 번호가 붙어 있으며, $w$는 탁자의 너비이다. Krzysztof는 식사 중에 싸움이 일어나길 원하지 않으므로, 좌석 번호가 $i$와 $j$인 두 마피아의 합의에 도달하는 예상 시간을 $d$라 하면 $d \leq |i - j|$가 성립해야 한다고 정했다. 따라서 일부 좌석은 비어 있을 수 있다. 손님들을 앉힐 수 있는 탁자의 최소 너비를 구하시오.

첫 줄에 정수 $Z \le 10^6$가 주어지며, 이는 다음 줄들에 설명된 테스트 케이스의 수이다.

각 테스트 케이스의 첫 줄에는 마피아의 수를 나타내는 정수 $n$이 하나 주어진다. 다음 $n - 1$개의 줄은 서로 친구인 마피아 쌍을 설명한다. $i$번째 쌍은 세 양의 정수 $a\_i$, $b\_i$, $c\_i$로 주어지며, 이는 마피아들의 번호와 그들 사이에서 직접 합의에 도달하는 예상 시간이다.

각 테스트 케이스마다 프로그램은 탁자의 최소 너비를 출력해야 한다.

• $n \geq 3$
• 모든 테스트 케이스에 걸친 $n$의 합은 $10^6$을 넘지 않는다.