지하철 시간 계산

스톡홀름은 대부분의 현대 도시와 마찬가지로 잘 갖춰진 대중교통 체계를 운영한다. 그 중심은 지하철이다. 노선도는 지하철 노선들이 어떻게 이어지는지를 보여준다. 그림 8을 참고하라.

그림 8: 스톡홀름 지하철 노선도

이 문제에서는 지하철 노선도가 항상 트리 모양이라고 가정한다. 실제 스톡홀름 노선도는 녹색 노선과 파란색 노선이 사이클을 이루기 때문에 완전한 트리가 아니다.

노선도는 기하 정보, 즉 역 사이의 거리와 이동 시간을 거의 알려주지 않는다. 예를 들어 스톡홀름 학생들은 Tekniska Högskolan(왕립공과대학)과 Universitetet(스톡홀름 대학교) 사이의 거리가 꽤 멀다는 것을 알지만, 노선도에는 이것이 나타나지 않는다.

인접한 모든 역 쌍 사이의 이동 시간을 적어 넣어 노선도를 보강하는 프로그램을 작성하라. 이동 시간은 이미 알려져 있으므로 직접 잴 필요는 없다. 실제 이동 시간은 초 단위이지만, 노선도에는 정수 분 단위의 추정값을 적어야 한다.

가장 단순한 방법은 모든 이동 시간을 가장 가까운 분으로 반올림하는 것이다. 그러나 이 방법은 누적 오차를 크게 키울 수 있다. 스톡홀름 노선도에서 이 방식을 쓰면 일부 역 쌍의 총 이동 시간에 최대 15분의 오차가 생길 수 있다. 그래서 프로그램은 일부 이동 시간은 올리고 나머지는 내려도 된다. 반올림은 임의의 두 역 사이 누적 오차의 최댓값이 최소가 되도록 해야 한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 역의 개수 $N$($1 \le N \le 100$)으로 시작한다. 역은 1부터 $N$까지의 정수로 구분한다. 이어지는 $N-1$개의 줄에는 세 정수 $a$, $b$, $t$($1 \le a, b \le N$, $1 \le t \le 300$)가 주어지며, 이는 역 $a$와 역 $b$가 인접해 있고 두 역 사이를 이동하는 데 $t$초가 걸린다는 뜻이다. 역에서 열차가 정차하는 시간은 무시한다.

마지막 테스트 케이스 다음 줄에는 0이 단독으로 주어진다.

각 테스트 케이스마다 케이스 번호(1부터 시작)를 출력한 뒤, 인접한 역 쌍의 이동 시간을 최적으로 반올림했을 때 임의의 두 역 사이 이동 시간에서 생기는 오차의 최댓값을 초 단위로 출력하라. 출력 형식은 샘플 출력을 따른다.