Сумма XOR

Задано дерево с $n$ вершинами. Ребра дерева имеют вес только $0$ или $1$. Найдем XOR сумму между всеми парами вершин. Вычислите сумму всех XOR сумм.

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

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

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

Выведите сумму XOR сумм между всеми парами вершин.

Примеры