트리 위의 로봇

최근 보리는 생일 선물로 로봇을 받았다. 그는 오래 고민하지 않고 바로 로봇을 시험해 보기로 했다. 보리는 손에 있던 재료로 시험장을 만들었다. 수학적으로 이 시험장은 사이클이 없는 연결된 무방향 그래프이며, 각 간선에는 강도 $w_i$가 있다.

보리는 로봇을 무작위로 고른 정점에 놓고 작동시켰다. 로봇의 알고리즘은 다음과 같이 동작한다. 매번 현재 정점에서 나가는 모든 간선을 살펴보고, 그중 하나를 무작위로 골라 이동한다. 로봇이 간선을 지날 때마다 그 간선의 강도가 1씩 줄어든다. 강도가 0이 되면 그 간선은 삭제된다. 로봇이 서 있는 정점의 간선이 모두 삭제되었다면 로봇은 움직임을 멈춘다.

보리나 로봇이 여러 선택지 중에서 고를 때는 각 선택지를 같은 확률로 고른다.

로봇에는 경로 길이 카운터가 내장되어 있으며, 처음 값은 0이다. 로봇이 간선을 지날 때마다 카운터 값이 1 증가한다. 보리는 여행이 끝났을 때 경로 길이 카운터에 기록되는 값의 기댓값이 얼마인지 알고 싶어 한다.

첫째 줄에 정수 $n$ ($1 \le n \le 10$)이 주어진다. 이는 그래프의 정점 개수이다. 다음 $n-1$개의 줄에는 각각 세 정수 $a_i$, $b_i$, $w_i$ ($1 \le a_i, b_i \le n$, $1 \le w_i \le 15$)가 주어진다. 이는 정점 $a_i$와 $b_i$ 사이에 강도가 $w_i$인 간선이 있다는 뜻이다. 입력으로 주어지는 그래프는 연결되어 있음이 보장된다.

로봇 경로 길이의 기댓값을 실수 한 개로 출력한다. 절대 오차 또는 상대 오차가 $10^{-9}$를 넘지 않으면 정답으로 인정한다.

참고로 심사위원이 사용하는 컴파일러에서는 C++의 long double 값을 출력하면 제대로 동작하지 않는다. 불편을 드려 죄송하며, 다음 시즌에 고치겠다. 그때까지는 double 사용을 권장한다.