시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 256 MB0000.000%

문제

Недавно на день рождения Боре подарили робота. Недолго думая он решил сразу проверить его в действии. Из подручных средств Боря собрал полигон для испытаний. С математической точки зрения этот полигон можно считать связным ацикличным неориентированным графом. Причем каждое его ребро обладает некоторой прочностью wi.

Боря поставил робота в случайно выбранную вершину графа и запустил его. Алгоритм, который заложен в робота, действует следующим образом. Каждый раз он анализирует все исходящие из вершины ребра и перемещается по случайному из них. Каждый раз, когда по ребру проезжает робот, прочность этого ребра уменьшается на единицу. Если прочность ребра становится равна нулю, то ребро удаляется. Если робот стоит в вершине, у которой все ребра были удалены, то он прекращает свое движение.

Всякий раз делая случайный выбор из нескольких вариантов, Боря или робот выбирают любой из них с равной вероятностью.

В роботе есть встроенный счетчик длины пути. Изначально его значение установлено на ноль. Каждый раз, когда робот перемещается по некоторому ребру, значение счетчика увеличивается на единицу. Боре стало интересно чему равно математическое ожидание числа, которое будет записано в счетчике длины пути в конце путешествия.

입력

Первая строка содержит одно целое число n (1 ≤ n ≤ 10) — количество вершин в графе. Следующая n-1 строка содержит по три целых числа aibi и wi (1 ≤ aibi ≤ n, 1 ≤ wi ≤ 15). Каждая такая строка обозначает, что существует ребро между вершинами ai и bi с прочностью wi. Гарантируется, что граф, который задан во входных данных, является связным.

출력

Выведите одно вещественное число — математическое ожидание длины пути робота. Ответ будет считаться правильным, если его абсолютная или относительная погрешность не превышает 10-9.

Обратите внимание, что вывод чисел типа long double в C++ некорректно работает в той версии компилятора, которая используется жюри. Мы приносим свои извинения, и обязательно исправим это в следующем сезоне, но пока рекомендуем использовать тип double.

예제 입력 1

4
1 2 1
1 3 1
1 4 2

예제 출력 1

2.416666666666667