어디로 불러야 할까?

Gooli는 언덕이 많은 지역에 건물 $B$개를 보유한 대기업이다. 건물에는 1부터 $B$까지 번호가 붙어 있다.

작년에 Gooli는 건물 사이에 미끄럼틀을 설치했다. 지금은 이 미끄럼틀이 건물 간 이동에 가장 많이 쓰이는 수단이다. 흡입 기술이 적용되어 모든 미끄럼틀은 양방향으로 쓸 수 있다. 일부 미끄럼틀은 굴곡이 있어서 길이가 상식과 맞지 않을 수 있다. 예를 들어 삼각 부등식을 만족하지 않을 수도 있다. 두 건물 사이에 미끄럼틀은 최대 하나뿐이다.

Gooli는 CEO가 다른 중요한 인물들과 통화할 수 있도록 특수 보안 전화기를 설치하려고 한다. 어느 건물에서 출발하든 전화기까지 미끄럼틀로 이동하는 거리를 최소화해야 CEO가 짧은 시간에 도착할 수 있다. Gooli에는 새 미끄럼틀을 지을 탄소 킬로튜브가 더 없고, CEO는 다른 교통수단을 쓰지 않는다. 따라서 보안팀은 기존 미끄럼틀만으로 도달할 수 있는 최적의 위치를 찾아야 한다. 위치는 건물일 수도 있고 미끄럼틀 위의 한 점일 수도 있다.

CEO는 미끄럼틀을 타고 건물에 도착한 뒤, 그 건물에서 시작하는 다른 미끄럼틀을 타고 목적지에 닿을 때까지 이동할 수 있다. 끝까지 탄 미끄럼틀은 전체 길이가 거리에 더해진다. 미끄럼틀에 들어갔다가 전화기를 찾아 중간에 멈추면, 실제로 지나온 부분의 길이만 더해진다. 거리는 미끄럼틀의 길이로만 잰다. 새 미끄럼틀로 옮겨 타거나 전화기로 가기 위해 건물 안에서 이동한 거리는 0으로 본다.

전화기의 최적 위치를 찾고, 그 위치에서 가장 먼 건물까지의 거리를 출력한다. 최적 위치가 여럿이어도 거리는 항상 같다.

첫 줄에 테스트 케이스 개수 $T$가 주어진다. 각 테스트 케이스는 건물 수 $B$가 적힌 줄로 시작한다. 이어서 $B-1$개의 줄이 주어진다. $i = 2, 3, \ldots, B$에 대해 $(i-1)$번째 줄에는 $D_{i1}, D_{i2}, \ldots, D_{i(i-1)}$이 주어진다. $D_{ij}$는 건물 $i$와 건물 $j$ 사이에 미끄럼틀이 없으면 $-1$이고, 있으면 그 미끄럼틀의 길이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 최적의 전화기 위치에서 가장 먼 건물까지의 거리다. 절대 오차 또는 상대 오차가 $10^{-6}$ 이내이면 정답으로 인정한다.

• $1 \le T \le 100$.
• $2 \le B \le 50$.
• 모든 건물은 미끄럼틀만으로, 필요하면 중간 건물을 거쳐 서로 도달할 수 있다.
• 모든 $i, j$에 대해 $D_{ij} \ne 0$이다.

마지막 두 케이스는 Small 데이터셋에는 나오지 않는다.

Case #1에서 모든 건물은 한 직선 위에 있다. 최적 위치는 그 선의 중점뿐이다. 다른 곳을 고르면 양 끝 건물 중 하나가 더 멀어지기 때문이다.

Case #2는 정삼각형이다. 세 건물 중 어느 것을 골라도 최적 위치가 된다.

Case #3도 삼각형이지만 변의 길이가 서로 다르다. 어떤 건물을 골라도 가장 먼 건물까지의 거리는 최소 3이다. 반면 길이 3인 미끄럼틀 위에서 건물 3으로부터 0.5 떨어진 지점을 고르면, 가장 먼 건물까지의 거리는 2.5로 줄어든다.

Case #4에서 최적 위치는 건물 1과 건물 3 사이에 있는 길이 10인 미끄럼틀 위다. 건물 3에서 1.5, 건물 1에서 8.5 떨어진 지점이다.