Батьки подарували Роману неорієнтований зв'язний зважений граф з $n$ вершинами та $n - 1$ ребрами. Роман бажає знайти сумарну довжину усіх шляхів у графі. Довжина шляху дорівнює сумі довжин ребер в ньому. Роман вважає, що шлях з $u$ в $v$ такий же самий, як і з $v$ в $u$, тому він ці шляхи не розрізняє. \InputFile Перший рядок містить кількість вершин у графі $n\:(2 \le n \le 10^5)$. Наступні $n - 1$ рядків описують ребра. Кожний рядок містить три цілі числа: номери вершин, сполучені ребром (вершини пронумеровані числами від $1$ до $n$), та вагу ребра. \OutputFile Вивести суму довжин усіх шляхів, обчислену за модулем $10^9$. \includegraphics{https://static.e-olymp.com/content/1c/1c9962225b484b4be775b21ea4f0cae761cb1c5a.gif}