배선 수리

동료 승무원들과 함께 우주선 The Skeld에 타고 있다. 그런데 중앙 전력 시스템을 점검하던 중, 중앙 전력 시스템의 중요한 배선 설비 하나가 파괴된 것을 발견했다. 엔진 고장을 막으려면 이 설비를 서둘러 수리해야 한다.

설비는 $N$개의 노드와 $M=\frac{N(N-1)}{2}$개의 전선으로 이루어져 있다. 설비 안의 서로 다른 두 노드 쌍은 모두 전선으로 연결되어 있다. 원래 $M$개의 전선에는 각각 태그가 정확히 하나씩 붙어 있었다. 각 태그에는 양의 정수 값이 적혀 있고, 서로 다른 태그가 같은 값을 가질 수도 있다. 그러나 파괴로 인해 모든 태그가 전선에서 떨어져 바닥에 흩어졌다. 다행히 바닥에서 $M$개의 태그를 모두 주웠다. 이제 설비를 수리하려면 모든 태그를 전선에 두 번 다시 붙여 재부팅 시퀀스를 작동시켜야 한다.

모든 전선에 태그가 붙어 있는 설비에 대해, 설비의 비용을 최소 신장 트리의 비용, 즉 주어진 전선 집합만으로 모든 노드를 연결하는 전선 부분집합의 최소 비용으로 정의한다. 여기서 전선 집합의 비용은 그 집합에 속한 모든 전선의 태그 값의 합이다.

재부팅 시퀀스는 두 단계로 작동한다. 먼저, 설비의 비용을 최소화하도록 태그를 붙인다. 그다음, 모든 태그를 떼어낸 뒤 설비의 비용을 최대화하도록 태그를 붙인다.

각 설비의 비용을 계산하시오.

첫째 줄에는 노드의 수를 나타내는 정수 $N$이 주어진다. ($2 \le N \le 100$)

둘째 줄에는 $M=\frac{N(N-1)}{2}$개의 태그 값을 나타내는 양의 정수 $C_1, C_2, \cdots, C_M$이 주어진다. ($1 \le C_i \le 2 \cdot 10^9$)

한 줄에 두 정수를 출력한다. 첫 번째는 설비의 최소 비용, 두 번째는 설비의 최대 비용이어야 한다.