바위 정원

바이트지방의 자작(Vicomte de Bajteaux)은 유명한 바위 수집품을 가지고 있다. 지금까지는 궁전 지하실에 보관해 왔지만, 이제 넓은 정원에 전시하기로 했다.

정원은 각 변의 길이가 $10^9$인 직사각형이며, 각 변은 동서 방향과 남북 방향에 평행하다. 자작은 바위마다 놓일 지점을 정한 뒤, 그 지점의 남쪽 변까지의 거리와 서쪽 변까지의 거리를 하인들에게 알려 주었다. 그런데 두 거리를 어떤 순서로 적었는지는 말해 주지 않았다. 어떤 바위는 남북 방향 거리(세로 좌표, 즉 y 좌표)를 먼저 적었고, 다른 바위는 동서 방향 거리(가로 좌표, 즉 x 좌표)를 먼저 적었던 것이다. 하인들은 이를 모른 채 통상적인 방식대로 첫 번째 수를 x 좌표로 삼아 모든 바위를 놓았다.

수집품을 보호하기 위해 자작은 울타리를 두르려 한다. 미관을 위해 울타리는 정원의 변에 평행한 직사각형이어야 하고, 그 전체 길이(둘레)는 될 수 있는 한 짧아야 한다. 바위는 두 좌표를 서로 맞바꾸는 방식으로만 옮길 수 있다(x로 쓰던 거리와 y로 쓰던 거리를 뒤바꾼다). 즉 두 좌표 값의 집합은 그대로 유지된다. 직사각형은 선분이나 한 점으로 줄어들어도 된다.

하인들은 울타리를 가능한 한 짧게 만들고 싶고, 가장 짧게 만드는 여러 방법 중에서 옮기는 바위들의 무게 합이 최소가 되도록 하고 싶다. 바위 하나를 옮긴다는 것은 그 두 좌표를 맞바꾼다는 뜻이며, 비용은 그 바위의 무게와 같다.

바위들의 현재 위치와 무게가 주어질 때, 가능한 최소 울타리 길이와, 그 길이를 얻기 위해 옮겨야 하는 바위들의 최소 무게 합을 구하여라.

첫째 줄에 바위의 개수 $n$ ($2 \le n \le 10^6$)이 주어진다. 다음 $n$개의 줄에는 각각 세 정수 $x_i$, $y_i$, $m_i$ ($0 \le x_i, y_i \le 10^9$, $1 \le m_i \le 2000$)가 주어지며, 이는 $i$번째 바위의 현재 두 좌표와 무게를 나타낸다. 순서를 무시했을 때 같은 좌표 쌍을 가지는 두 바위는 존재하지 않는다.

공백으로 구분된 두 정수를 출력한다. 첫 번째 값은 가능한 최소 울타리 길이(둘레)이고, 두 번째 값은 그 길이를 얻기 위해 두 좌표를 맞바꿔야 하는 바위들의 최소 무게 합이다.