24459번 - 회로의 저항

문제

어떤 PCB (Printed Circuit Board)에는 노드 $N$개가 있으며, 저항 $N-1$개가 그 사이를 사이클 없이 연결하고 있다.

우리는 PCB의 정보가 주어질 때, 두 가장자리 노드를 연결해 얻을 수 있는 가장 큰 저항값과 가장 작은 저항값을 구할 것이다. 이때 가장자리 노드란 저항 한 개만 연결된 노드이다.

위 그림에서 두 가장자리 노드를 연결하는 가장 큰 저항값과 가장 작은 저항값을 찾으면 아래와 같은 그림이 나온다.

위 그림은 두 가장자리 노드를 연결하는 가장 큰 저항값을 만드는 데 사용되는 저항이 있는 부분에 빨간색으로 나타낸 것이다. 이때 회로에서 만든 가장 큰 저항값은 20ドル \Omega$이다.

위 그림은 두 가장자리 노드를 연결하는 가장 작은 저항값을 만드는 데 사용되는 저항이 있는 부분에 나타낸 것이다. 이때 회로에서 만든 가장 작은 저항값은 9ドル \Omega$이다.

PCB에서 두 가장자리 노드를 연결해 얻을 수 있는 최대 저항과 최소 저항을 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 노드의 개수 $N$이 정수로 주어진다. $(2 \le N \le 100,000円)$

그다음 $N-1$줄에 걸쳐 각 줄에는 간선의 정보로 세 정수 $p,ドル $q,ドル $w$가 공백으로 구분되어 주어진다. $(0 \le p, q < N,\ p ≠ q,\ 1 \le w \le 10,000円)$

$p$와 $q$는 저항이 연결하는 노드의 번호이고, $w$는 저항의 값이다. (단위는 $\Omega$)

출력

두 가장자리 노드를 연결하는 가장 큰 저항값과 가장 작은 저항값을 한 줄에 하나씩 순서대로 출력한다.

제한

노트

그림에 있는 저항의 값은 실제와 다르다.