eolymp
Задачі

Сума

Сума

Батьки подарували Роману неорієнтований зв'язний зважений граф з n вершинами та n - 1 ребрами. Роман бажає знайти сумарну довжину усіх шляхів у графі. Довжина щляху дорівнює сумі довжин ребер в ньому. Роман вважає, що шлях з u в v такий же самий, як і з v в u, тому він ці шляхи не розрізняє.

Вхідні дані

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

Вихідні дані

Вивести суму довжин усіх шляхів, обчислену за модулем 109.

prb2157.gif

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3
1 2 1
1 3 3
Вихідні дані #1
8
Вхідні дані #2
6
1 2 5
1 3 1
2 4 2
2 5 4
2 6 3
Вихідні дані #2
90

Пояснення: Пояснення до прикладу. Усі шляхи графу: 1->2, 1->3, 2->1->3, сума їх довжин дорівнює 1 + 3 + 4 = 8.

Джерело 2011 International Collegiate Programming Contest, Ukraine, Quarter-Final, May 19