트램

전기 요금이 계속 오르면서 바이토시아 시장은 예산을 크게 삭감할 수밖에 없었고, 그 여파로 최근 시내 트램이 운행을 멈췄다. 시민들은 모두 붐비는 버스에 시달리게 되어 교통 상황이 크게 나빠졌다. 다행히 한 가지 희망이 있다. 바이토시아는 비트 인프라부로부터 보조금을 받을 수 있으며, 당신은 그 신청서를 준비하는 일을 돕고 있다.

바이토시아의 트램 선로망은 $n$개의 교차로와 $n - 1$개의 선로 구간으로 이루어져 있으며, 어떤 교차로에서든 선로를 따라 다른 모든 교차로로 갈 수 있다(즉, 선로망은 트리를 이룬다). 선로 구간이 정확히 하나만 연결된 교차로에는 트램 회차 루프가 있다. 루프의 개수를 $k$라 하자. 시는 트램을 $\lfloor k / 2 \rfloor$대 보유하고 있다. 각 트램은 서로 다른 두 루프를 잇는 자신만의 노선을 달리며, 같은 교차로를 두 번 지나지 않는다. 서로 다른 트램의 노선은 같은 교차로나 선로 구간을 공유할 수 있지만, 하나의 루프에서 시작하거나 끝나는 노선은 최대 하나뿐이다.

트램이 하루에 쓰는 전기 비용은 노선의 길이에 비례한다. 따라서 시장이 신청하는 보조금 총액은 노선 계획을 어떻게 세우느냐에 크게 좌우된다. 시장은 가능한 모든 올바른 노선 계획에 대해 얻을 수 있는 노선 길이 총합의 최솟값과 최댓값을 알고 싶어 한다. 이 두 값을 구하라.

첫 번째 줄에 교차로의 개수 $n$ ($1 \le n \le 100\,000$)이 주어진다. 교차로는 $1$번부터 $n$번까지 번호가 매겨져 있다. 이어지는 $n - 1$개의 줄 중 $i$번째 줄에는 세 정수 $a_i$, $b_i$, $c_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$, $1 \le c_i \le 1\,000\,000$)가 주어지며, 이는 $i$번째 선로 구간이 잇는 두 교차로의 번호와 그 구간의 길이를 뜻한다.

정확히 두 줄을 출력한다. 첫 번째 줄에는 올바른 계획으로 얻을 수 있는 트램 노선 길이 총합의 최솟값을, 두 번째 줄에는 그 최댓값을 출력한다. 트램이 한 대도 없다면(루프가 두 개 미만이면) 두 줄 모두 $0$을 출력한다.