숨겨진 미로

헬렌과 헨리는 히든랜드에서 인기가 많은 방송 프로그램 "숨겨진 미로"의 팬이다. 이 프로그램에서는 참가자 두 명, 보통은 부부인 두 사람이 방 $n$개와 방을 잇는 터널로 이루어진 미로를 달린다. 터널은 서로 다른 두 방을 잇고, 같은 두 방을 잇는 터널이 둘 이상 있는 경우는 없다.

프로그램이 시작되면 두 참가자는 서로 다른 방에 놓인다. 두 사람은 제한 시간이 끝나기 전에 만나야 한다. 터널 하나를 지나려면 그 터널의 단서를 찾아야 하는데, 단서는 작은 종이에 적힌 양의 정수다.

제한 시간이 끝나기 전에 터널 안에서 만나고 만난 터널의 단서까지 찾으면 두 사람이 승리한다. 상금은 두 사람이 찾은 단서를 모두 정렬한 다음 중앙값을 취해 정한다. 찾는 단서의 개수는 항상 홀수가 되도록 게임을 짠다.

미로는 회차가 바뀌어도 그대로다. 헬렌과 헨리는 미로 전체를 지도로 그려 두었다. 터널을 각각 최대 한 번씩만 지난다고 하면 임의의 두 방 사이의 경로는 정확히 하나다.

미로를 지은 회사에서 일했던 힐러리는 인터뷰에서 미로를 다음 무작위 알고리즘으로 만들었다고 밝혔다.

1. 방의 개수 $n$을 정한다. $1$번부터 $n$번까지 번호를 붙인 방 $n$개를 만든다.
2. $1$ 이상 $n$ 이하의 정수 $i$와 $j$를 각각 균등하게 무작위로 고른다.
3. 방 $i$와 방 $j$가 같거나 이미 터널로 이어져 있으면 2번으로 돌아간다.
4. 방 $i$와 방 $j$를 잇는 터널을 만든다. 이제 어떤 두 방 사이에도 터널로 된 경로가 있으면 멈추고, 아니면 2번으로 돌아간다.

터널마다 단서가 정확히 하나 있고 그 값은 회차가 바뀌어도 변하지 않는다. 헬렌과 헨리는 지도에 터널마다 단서 값을 적어 두었다.

단서를 찾고 터널을 지나 옆 방까지 가는 데 1분이 걸린다. 방에서 터널 한가운데까지 달리는 데는 30초가 걸리고, 두 사람은 마지막에 터널 한가운데에서 만난다. 제한 시간은 두 사람이 최적으로 움직일 때만 만날 수 있을 만큼만 준다. 즉 두 사람은 최단 경로로 서로에게 달려가고, 단서 찾기에 실패하지 않으며, 최단 경로에 없는 터널로는 들어가지 않는다. 따라서 두 사람이 찾는 단서는 처음 놓인 두 방을 잇는 최단 경로에 있는 터널의 단서 전부이고, 만나는 터널의 단서도 여기에 들어간다. 터널 한가운데에서 만나도록, 처음 놓이는 두 방 사이의 최단 경로 길이는 항상 홀수다.

시작하는 두 방은 최단 경로 길이가 홀수인 방 쌍 전체에서 균등하게 무작위로 정해진다. 두 사람이 받게 될 상금의 기댓값을 구하라.

첫 줄에 방의 개수 $n$ ($2 \le n \le 30000$)이 주어진다. 다음 $n - 1$개의 줄에는 각각 세 정수 $u_i$, $v_i$, $c_i$ ($1 \le u_i, v_i \le n$, $1 \le c_i \le 10^6$)가 주어진다. $i$번 터널이 방 $u_i$와 방 $v_i$를 잇고 값이 $c_i$인 단서를 담고 있다는 뜻이다. 미로는 항상 문제에 적힌 무작위 알고리즘으로 만들어진다.

상금의 기댓값을 기약분수 p/q 꼴로 한 줄에 출력한다. $p$와 $q$는 정수이고 $q \ge 1$, $\gcd(p, q) = 1$이다. $q$가 $1$일 때도 p/q 꼴로 출력한다.

처음 놓인 두 방을 잇는 최단 경로의 터널 개수는 홀수이므로 중앙값은 하나로 정해진다. 값이 같은 단서가 여러 터널에 있어도 중앙값은 달라지지 않는다.