29294번 - Паша и тропинки 스페셜 저지다국어

문제

Как Вы уже поняли, дядя Паша любит гулять. Сегодня на улице стоит очень хорошая погода, поэтому, недолго думая, Паша оделся, взял ноутбук и пошел в парк поблизости.

Посмотрев на карту, расположенную около входа, Паша понял, что парк представляет собой дерево, где тропинки --- рёбра, а их пересечения --- вершины дерева. Прикинув свою среднюю скорость, Паша посчитал для каждой тропинки, сколько ему нужно времени для её прохождения.

Однако не все так просто. Некоторые тропинки в парке ещё не высохли после дождей, поэтому они грязные. Но Пашу это не останавливает, он решил посчитать среднее время, которое он потратит на прохождение простого пути, в котором есть хотя бы одна чистая тропинка. Более формально, Пашу интересует среднее время прохождения пути между двумя вершинами по всем таким парам вершин, что на пути между ними есть хотя бы одна чистая дорожка.

Тут к нему подошел друг Филя, с которым Паша договорился встретиться. Паша достал ноутбук, дал его Филе и попросил посчитать его ответ на этот непростой вопрос. Филя --- так себе программист, поэтому он скорее всего не справится с этой задачей. Помогите ему!

입력

В первой строке входного файла содержится число $n$ (1ドル \le n \le 10^5$) --- количество пересечений тропинок в парке.

В следующих $n - 1$ строке входного файла дана информация о тропинках. В каждой строке записано четыре числа $a, b, c, d$ (1ドル \le a, b \le n, 0 \le c \le 10^4, 0 \le d \le 1$) --- номера вершин, между которыми проведена $i$-ая тропинка, время, за которое Паша пройдет эту тропинку, и число, описывающее состояние тропинки (0 --- грязная тропинка, 1 --- чистая).

출력

В единственной строке выходного файла выведите ответ на задачу.

Ответ будет считаться верным, если относительная погрешность не будет превосходить 10ドル^{-6}$.

제한

노트