Родители подарили Роману неориентированный связный взвешенный граф с n вершинами и n−1 ребрами. Роман хочет найти суммарную длину всех путей в графе. Длина пути равна сумме длин ребер в нем. Роман считает, что путь из u в v такой же как и из v в u, поэтому он не различает их.
Первая строка содержит количество вершин в графе n(2≤n≤105). Следующие n−1 строк описывают ребра. Каждая строка содержит три целых числа: номера вершин, соединенных ребром (вершины пронумерованы числами от 1 до n), и вес ребра.
Вывести сумму длин всех путей, вычисленную по модулю 109.