ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1371. Грузоперевозки

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Компания Advanced Carriage Messaging, занимающаяся грузоперевозками, имеет разветвлённую сеть филиалов. Бизнес ACM идёт в гору, и компания решила организовать новые филиалы. Но прежде, чем это сделать, руководство компании решило проанализировать, насколько эффективно работает доставка товаров между филиалами. Для этого и требуются Ваш опыт и знания.
Схема доставки товаров между филиалами устроена так, что из любого филиала товар можно перевезти в любой другой (возможно через другие филиалы), причём единственным способом. Также известно t[i, j] — время доставки товара между двумя филиалами (c номерами i и j), между которыми есть прямое сообщение. От Вас требуется определить среднее время на доставку товара между филиалами, то есть величину sum (t[i, j]) / (N*(N − 1)), где суммирование ведётся по 1 ≤ i, jN и ij.

Исходные данные

В первой строчке указано число N (2 ≤ N ≤ 50000) — количество филиалов в компании ACM. Далее идёт N−1 строка, каждая из которых содержит тройку чисел ai, bi, ci, где ai, bi (1 ≤ ai, biN) — номера филиалов, имеющих прямое сообщение между собой, а ci (0 ≤ ci ≤ 1000; все ci целые) — время доставки товара между этими филиалами.

Результат

Выведите единственное число — среднее время доставки товара между филиалами с точностью 4 знака после десятичной точки.

Пример

исходные данныерезультат
4
1 2 1
2 3 1
2 4 1
1.5
Автор задачи: Александр Клепинин (идея — Ден Расковалов)
Источник задачи: IX Чемпионат Урала по программированию. Екатеринбург, УрГУ, 19-24 апреля 2005г.