최소 지연 시간

2222년이다. 우주 전체가 탐사되었고 모든 행성에 정착지가 세워져 있다. 여러분은 그중 한 정착지에 살고 있다.

생활은 대부분 편하지만 심각한 문제가 하나 있다. 다른 행성과의 인터넷 연결 지연 시간이 지나치게 길다.

해결책은 모든 행성 사이에 Bonded, Astronomically Paired Cables를 설치하는 것이다. 그러면 인터넷이 매우 빨라진다. 다만 두 행성 사이에 케이블을 놓는 일은 생각보다 어렵다. 그래서 첫 시제품은 서로 가장 가까운 두 행성을 잇는다.

우주는 각 차원의 길이가 $10^9$ 광년인 큰 정육면체로 모델링된다. 정지해 있는 행성은 $10^5$개이다. 모든 좌표는 $0$부터 $10^9$까지의 정수 중에서 서로 독립적으로 균등하게 뽑힌 값이다.

행성들의 위치가 주어질 때, 임의의 두 행성 사이의 최소 유클리드 거리를 구하라.

첫 줄에 행성의 개수를 나타내는 정수 $n$이 주어진다. 이어지는 $n$개의 줄에는 행성 하나의 좌표를 나타내는 정수 $x$, $y$, $z$가 주어진다 ($0 \le x, y, z < 10^9$).

제출물은 정확히 100개의 테스트 케이스에서 실행되며, 모든 테스트 케이스의 $n$은 $10^5$이다. 예제는 더 작고 형식을 보여 주기 위한 것이다. 실행할 때마다 새로 생성된 무작위 테스트 케이스가 사용된다.

임의의 두 행성 사이의 최소 유클리드 거리를 출력한다. 절대 오차 또는 상대 오차가 $10^{-6}$ 이하이면 정답으로 인정한다.