로봇 챌린지

당신은 로봇 챌린지에 로봇을 출전시켰다. 코스는 $100\text{m} \times 100\text{m}$ 공간에 설치된다. 공간 안의 특정 지점들이 목표점으로 지정되며, 이들에는 순서가 있다 — 목표 1, 목표 2 등이 있다. 로봇은 반드시 $(0,0)$에서 출발한다. 거기서 목표 1로 가서 1초 동안 멈추고, 목표 2로 가서 1초 동안 멈추고, 이런 식으로 계속한다. 마지막에는 반드시 $(100,100)$에 도달하여 그곳에서 1초 동안 멈춰야 한다.

$(0,0)$과 $(100,100)$을 제외한 각 목표점에는 그 목표를 지나치는 경우에 대한 시간 페널티가 있다. 즉, 로봇이 목표 1에서 목표 2를 건너뛰고 곧장 목표 3으로 가면 목표 2의 페널티가 부과된다. 일단 목표 3에 도달하면 다시 목표 2로 돌아갈 수 없다는 점에 유의하라. 목표들은 반드시 순서대로 방문해야 한다. 로봇은 각 목표점에서 1초 동안 멈추므로, 실수로 어떤 목표를 너무 일찍 방문하게 될 위험은 없다. 예를 들어 목표점 3이 목표점 1과 2 사이의 직선 위에 정확히 놓여 있다면, 로봇은 목표 1에서 목표 2로 곧장 이동하면서 멈추지 않고 목표 3 위를 지나갈 수 있다. 멈추지 않았으므로 심판은 로봇이 목표 3을 너무 일찍 방문했다고 오해하지 않으며, 따라서 목표 2의 페널티를 부과하지 않는다. 최종 점수는 로봇이 코스를 완주하여 $(100,100)$에 도달하는 데 걸린 시간(초)에 모든 페널티를 더한 값이다. 점수가 작을수록 좋다.

로봇은 기동성은 매우 뛰어나지만 조금 느리다. 속도는 $1\text{m/s}$이지만 방향은 매우 빠르게 바꿀 수 있다. 목표점에서 멈춰 있는 1초 동안 다음 목표점을 향해 손쉽게 방향을 돌릴 수 있다. 따라서 목표점 사이에서는 항상 직선으로 이동할 수 있다.

로봇이 조금 느리기 때문에, 실제로 어떤 목표까지 이동하기보다 그 목표를 건너뛰고 페널티를 감수하는 편이 유리할 수도 있다. 코스에 대한 설명이 주어질 때, 로봇이 얻을 수 있는 가장 좋은(가장 낮은) 점수를 구하여라.

입력에는 여러 개의 테스트 케이스가 주어진다. 각 테스트 케이스는 코스에 있는 목표의 개수를 나타내는 정수 $N$ $(1 \le N \le 1000)$이 적힌 한 줄로 시작한다. 이어지는 $N$개의 줄에는 각각 세 정수 $X$, $Y$, $P$로 목표가 설명된다. 여기서 $(X,Y)$는 코스 위의 위치이고 $(1 \le X, Y \le 99$, 단위는 미터$)$, $P$는 로봇이 그 목표를 지나칠 때 부과되는 페널티이다 $(1 \le P \le 100)$. 목표들은 순서대로 주어진다 — $N$ 다음의 첫 번째 줄이 목표 1, 그다음이 목표 2, 이런 식이다. 한 코스에 있는 모든 목표는 서로 다르다 — 코스 위의 한 위치에는 많아야 하나의 목표점만 존재한다. 입력의 끝은 하나의 $0$이 적힌 줄로 표시된다.

각 테스트 케이스마다, 해당 코스에서 가능한 가장 낮은 점수를 하나의 소수로 출력한다. 이 값은 (버림이 아니라) 반올림하여 소수점 아래 셋째 자리까지 출력한다. 각 답은 한 줄에 하나씩 출력하며, 답 사이에 빈 줄을 넣지 않는다.