Сума

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

Вхідні дані

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

Вихідні дані

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

Приклади