성

전쟁은 세계사에서 중요한 역할을 해 왔다. 현대의 전쟁과 달리 중세의 군대는 영주와 귀족의 사유 요새인 성을 점령하고 지키는 일에 주로 관심을 두었다. 공격하는 군대의 규모는 이런 건축적 걸작을 점령하고 지키는 능력에 중요한 요소였다.

그림 2

성을 점령하려면 최소한의 병사 수가 필요했다. 공격 중에 일부 병사가 죽을 것으로 예상되었다. 성을 점령한 뒤에는 다른 적의 공격에 대비해 성을 방어할 병사가 일부 남아 있어야 했다. 물론 그 수는 성마다 달랐다. 군대의 지휘관은 승리에 필요한 병사 수를 고려해야 했다. 예를 들어 그림 2의 지역 지도에는 다섯 개의 성이 있다. 오른쪽 아래의 성은 승리하는 공격을 벌이려면 최소 20명의 병사가 필요하다. 공격 중에 죽을 것으로 예상되는 병사는 없으며, 군대가 이동할 때 성에 10명의 병사를 남겨 두어야 한다.

이 문제에서는 특정 지역의 모든 성을 점령하고 지키는 데 필요한 군대의 최소 규모를 구해야 한다. 보안상의 이유로 지역의 어떤 두 성 사이에도 (양방향) 경로가 정확히 하나씩 있다. 점령되지 않은 성의 근처로 이동하면 그 성에 대한 공격이 시작된다. 어떤 성이든 군대가 어떻게 거기에 도착했는지와 상관없이 처음 공격할 성이 될 수 있다. 성을 하나 점령하면 그 성을 방어할 병사를 필요한 수만큼 남기고, 남은 군대는 아직 점령되지 않은 성이 있으면 다른 성으로 이동해 전투를 벌인다. 군대는 이미 점령한 성의 근처를 안전하게 지나갈 수 있다. 그러나 공격의 위험 때문에 군대는 두 성 사이의 경로를 최대 두 번(즉, 각 방향으로 최대 한 번)까지만 지나갈 수 있다.

입력은 서로 다른 지역에 대응하는 여러 테스트 케이스를 포함한다. 각 지역의 성에 대한 설명은 여러 줄에 걸쳐 있다. 첫째 줄에는 지역의 성 개수인 정수 n ≤ 100이 주어진다. 다음 n개 줄에는 각각 세 정수 a, m, g (1 ≤ a ≤ 1000, 0 ≤ m ≤ a, 1 ≤ g ≤ 1000)가 주어지는데, 이는 특정 성을 성공적으로 공격해 점령하는 데 필요한 최소 병사 수, 공격 중에 죽을 것으로 예상되는 병사 수, 성을 방어하기 위해 성에 남겨 두어야 하는 병사 수이다. 성은 1부터 n까지 번호가 매겨지며, 성을 설명하는 입력 줄은 성 번호가 증가하는 순서로 주어진다. 테스트 케이스의 나머지 n – 1개 줄에는 직접 경로로 연결된 두 성의 번호가 주어진다.

마지막 지역의 설명 뒤에는 0이 포함된 줄이 온다.

각 테스트 케이스마다 케이스 번호와 지역의 모든 성을 정복하는 데 필요한 군대의 최소 병사 수를 출력한다. 샘플 출력에 나온 형식을 따르라.