Родители подарили Роману неориентированный связный взвешенный граф с $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}