e-olymp
Соревнования

ADA Classes - Depth First Search

Сумма

Родители подарили Роману неориентированный связный взвешенный граф с n вершинами и n - 1 ребрами. Роман хочет найти суммарную длину всех путей в графе. Длина пути равна сумме длин ребер в нем. Роман считает, что путь из u в v такой же как и из v в u, поэтому он не различает их.

Входные данные

Первая строка содержит количество вершин в графе n (2n105). Следующие n - 1 строк описывают ребра. Каждая строка содержит три целых числа: номера вершин, соединенных ребром (вершины пронумерованы числами от 1 до n), и вес ребра.

Выходные данные

Вывести сумму длин всех путей, вычисленную по модулю 109.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
3
1 2 1
1 3 3
Выходные данные #1
8

Объяснение: Объяснение к примеру. Все пути на графе: 1 - 2, 1 - 3, 2 - 1 - 3, сумма их длин равна 1 + 3 + 4 = 8.

Источник 2011 International Collegiate Programming Contest, Ukraine, Quarter-Final, May 19