Сумма

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

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

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

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

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

Примеры