어디로 전화할 건가?

Gooli는 언덕이 많은 지역에 B개의 건물을 소유한 거대한 회사이다. 건물에는 1부터 B까지 번호가 매겨져 있다.

작년에 Gooli는 건물 사이에 여러 미끄럼틀을 건설했으며, 이제 이것들은 건물 사이에서 가장 선호되는 이동 수단이다. 미끄럼틀은 흡착 기술로 개량되어 양방향으로 이용할 수 있으므로, 두 건물 사이의 미끄럼틀을 이용해 어느 방향으로든 두 건물 사이를 이동할 수 있다. 일부 미끄럼틀은 굽이진 형태로 건설되었으므로 그 길이가 반드시 상식에 부합하지는 않는다. 예를 들어, 반드시 삼각 부등식을 만족하지는 않는다. 또한, 어떤 건물 쌍 사이에도 미끄럼틀은 최대 하나만 존재한다.

Gooli는 CEO가 다른 중요한 사람들과 대화할 수 있도록 특수한 초고도 보안 전화기를 설치할 위치를 정하려 한다. 어느 건물에서든 회의 장소까지 미끄럼틀로 이동하는 거리를 최소화하여, CEO가 어느 건물에서 출발하더라도 그곳에 도달하는 데 걸리는 시간을 최소화하려 한다. Gooli에는 미끄럼틀을 더 건설할 탄소 킬로튜브가 남아 있지 않고, CEO는 다른 어떤 이동 수단도 거부하므로, Gooli의 통신 보안 팀은 이미 존재하는 미끄럼틀만을 사용해 도달할 수 있는 최적의 위치를 찾아야 한다. 그 위치는 건물 안일 수도 있고 미끄럼틀 내부의 어느 지점일 수도 있다.

미끄럼틀을 이용해 이동할 때 CEO는 미끄럼틀을 타고 건물에 도착한 뒤, 그곳에서 시작하는 미끄럼틀을 타고 다른 건물에 도착하는 일을 원하는 위치에 도착할 때까지 계속할 수 있다. 한쪽 끝에서 다른 쪽 끝까지 이용한 미끄럼틀은 그 전체 길이가 총거리에 포함된다. 반면 CEO가 미끄럼틀에 진입한 뒤 전화기를 발견하여 그 내부에서 멈춘다면, 미끄럼틀에서 이용한 부분만 총거리에 포함된다. 거리를 측정할 때는 미끄럼틀에서 이동한 거리만 중요하다. 새 미끄럼틀로 이어지는 곳이나 전화기가 있는 곳까지 건물 내부에서 이동한 거리는 영으로 간주한다.

현재 존재하는 건물과 미끄럼틀이 주어질 때, 초고도 보안 전화기의 최적 위치 중 아무 위치나 찾아 그 위치에서 가장 먼 건물까지의 거리를 구할 수 있는가? 모든 최적 위치에서 이 거리는 같다는 점에 유의하라.

제한

1 ≤ T ≤ 100. 테스트 세트당 시간 제한: 100초. 메모리 제한: 1GB. 2 ≤ B ≤ 50. 중간 건물들을 거칠 수도 있으며, 미끄럼틀만을 사용해 모든 건물에서 다른 모든 건물로 도달할 수 있다. 모든 i, j에 대해 $D_{ij}$ ≠ 0.

작은 데이터 세트 (테스트 세트 1 - 공개)

모든 i, j에 대해 -1 ≤ $D_{ij}$ ≤ 2.

큰 데이터 세트 (테스트 세트 2 - 비공개)

모든 i, j에 대해 -1 ≤ $D_{ij}$ ≤ $10^{9}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 Gooli 캠퍼스의 건물 수를 나타내는 정수 B 하나가 있는 한 줄로 시작한다. 그다음 B - 1개의 줄이 주어진다. i = 2, 3, ..., B에 대해, 이 줄들 중 (i-1)번째 줄에는 (i-1)개의 정수 $D_{i1}$, $D_{i2}$, ..., $D_{i(i-1)}$가 주어진다. i번째 건물과 j번째 건물 사이에 미끄럼틀이 없으면 $D_{ij}$은 -1이고, 그렇지 않으면 그 미끄럼틀의 길이이다. 중간 건물들을 거칠 수도 있으며, 미끄럼틀만을 사용해 모든 건물에서 다른 모든 건물로 도달할 수 있다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y은 전화기의 최적 위치에서 그 위치로부터 가장 먼 건물까지의 거리이다. y이 정답과의 절대 오차 또는 상대 오차가 10^{-6} 이내이면 정답으로 간주한다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 관한 설명은 FAQ을 참고하라.

마지막 두 케이스는 작은 데이터 세트에 등장하지 않는다는 점에 유의하라.

케이스 #1에서 모든 건물은 일직선상에 있다. 다른 위치를 선택하면 선의 한쪽 끝에 있는 건물 하나가 더 멀어지므로, 당연히 유일한 최적 위치는 선의 중점이다.

케이스 #2은 정삼각형을 나타낸다. 세 건물 중 어느 곳이든 전화기의 최적 위치가 된다.

케이스 #3 역시 삼각형이지만, 변들의 길이가 서로 다르다. 어느 건물을 선택하더라도 가장 먼 건물까지의 거리는 적어도 3이다. 반면 길이가 3인 미끄럼틀 내부에서 건물 3로부터의 거리가 0.5인 위치를 선택하면, 가장 먼 건물까지의 거리가 2.5로 개선된다.

케이스 #4에서 최적 위치는 건물 1과 3 사이에 있는 길이 10의 미끄럼틀 내부이며, 건물 3로부터의 거리는 1.5이고 건물 1로부터의 거리는 8.5이다.