27304번 - 동우의 마음씨는 착할까 나쁠까

문제

고려대학교 사이버국방학과 동아리 MatKor에서는 정기적으로 한 명의 외부 강사를 초청하여 세미나를 진행한다. 그런데, MatKor 세미나를 이미 여러 번 진행해본 동우는 무언가를 설명할 때 모두가 집중하지 않아 결국 한 명씩 따로 설명해야 한다는 사실을 깨달았다. 이를 위해서 이번 학기부터는 1대 1 세미나로 진행하기로 하였다. 그리고 한 번의 세미나를 진행하는데 매우 많은 힘이 든다는 사실을 알게된 동우는 강사의 편의를 위해 하루에 한 번의 세미나만 진행하기로 하였다.

MatKor는 총 $N$명의 부원들로 구성되어 있고, 각 부원들은 서로 다른 마을에 거주하고 있다. 그리고 마을과 마을을 잇는 서로 다른 도로가 총 $N-1$개 존재한다. 임의의 두 마을에 대해 그 사이를 이동하는 경로는 하나만 존재함이 보장되며, 각 도로는 양방향으로 움직일 수 있다. 또한, 어떤 사람이든 상관없이 각 도로를 이동하고 나면 힘듦의 정도가 $c_i$만큼 증가한다고 한다. 그런데, MatKor 부원들이 거주하고 있는 마을은 특이해서 도로를 이동하고 나면 오히려 힘듦의 정도가 적어질 수도 있다. 즉, $c_i$의 값은 0ドル$ 또는 음의 정수일 수 있다. 이제 동우는 강사를 위해 새로운 집을 건설해주려고 한다. 단, 새로운 집은 이미 존재하는 마을 또는 도로 위에 건설할 수 있다. 만약, 집을 도로 위에 건설한다면 그 위치로부터 도로 양 끝의 마을로 이동할 때 증가하는 힘듦의 정도는 그 거리와 도로의 $c_i$ 값에 비례해서 증가하게 된다. 예를 들어, 1ドル$번 마을과 2ドル$번 마을을 잇는 도로가 있고 이 도로를 처음부터 끝까지 이동했을 때 5ドル$만큼 힘듦의 정도가 증가한다고 하자. 이 때, 강사의 집을 1ドル$번 마을과 2ドル$번 마을을 1ドル:2$로 내분하는 지점에 건설하게 된다면 그 지점으로부터 1ドル$번 마을까지는 ${5 \over 3}$만큼, 2ドル$번 마을까지는 ${10 \over 3}$만큼 힘듦의 정도가 증가하게 되는 것이다.

강사는 하루에 한 번씩 각 부원이 거주하는 마을로 이동하여 1대 1 세미나를 진행한 후, 다시 자신의 집으로 돌아온다. 단, 강사가 집으로 돌아올 때는 집에서 쉴 생각에 신이 나있기 때문에 지나온 경로의 $c_i$와 상관없이 힘듦의 정도가 변화하지 않는다고 한다. 그리고, 이 과정을 MatKor의 모든 부원들에 대해 한 번씩 진행해야 한다. 동우는 마음씨가 착할 수도 있고 나쁠 수도 있어, 강사가 느끼게 되는 힘듦의 정도를 최소화하거나 최대화하는 위치에 위치에 집을 건설해주고자 한다. 단, 강사가 집에서 각 마을로 이동할 때는 동일한 도로를 두 번 이상 지나지 않는 경로를 통해 이동하며, 같은 마을 내에서는 이동할 때는 힘듦의 정도가 변화하지 않는다. 동우를 위해 강사가 세미나를 진행할 때 느끼는 힘듦의 정도의 최솟값과 최댓값을 구해주자.

입력

첫 번째 줄에 부원의 수를 나타내는 정수 $N$ (2ドル \le N \le 5\times 10^5$)이 주어진다.

2ドル$번째 줄부터 $N$번째 줄까지 도로에 대한 정보가 주어진다. 각 줄에는 도로의 양 끝 마을을 뜻하는 서로 다른 두 정수 $a_i$ (1ドル \leq a_i \le N$)와 $b_i$ (1ドル \leq b_i \le N$), 그 도로를 지났을 때 힘듦의 정도의 변화량을 나타내는 정수 $c_i$ ($-10^7 \le c_i \le 10^7$)가 공백을 사이에 두고 주어진다.

출력

강사가 세미나를 진행하게 될 때 느끼는 힘듦의 정도의 최솟값과 최댓값을 공백을 사이에 두고 출력한다.

만약 답이 정수라면 그대로 출력하고, 정수가 아닌 유리수라면 기약분수 ${p\over q}$ (1ドル \le \lvert p\rvert,ドル 2ドル\le q$이며 $gcd(\lvert p\rvert,q)=1$)로 약분해 $p$/$q$의 형태로 출력한다.

정답이 유리수임을 증명할 수 있다.

제한

노트

동우의 마음씨는 착하다는 것이 정론이다.