F. Уникальные вхождения
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Задано дерево, состоящее из $$$n$$$ вершин. На каждом ребре написано целое число.

Пусть $$$f(v, u)$$$ будет равно количеству значений, которые встречаются ровно один раз на ребрах на простом пути между $$$v$$$ и $$$u$$$.

Посчитайте сумму $$$f(v, u)$$$ по всем парам вершин $$$v$$$ и $$$u$$$, для которых $$$1 \le v < u \le n$$$.

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

В первой строке записано одно целое число $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$) — количество вершин в дереве.

В каждой из следующих $$$n-1$$$ строк записаны три целых числа $$$v, u$$$ и $$$x$$$ ($$$1 \le v, u, x \le n$$$) — описание ребра: вершины, которое оно соединяет, и значение, написанное на нем.

Заданные ребра образуют дерево.

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

Выведите одно целое число — сумму $$$f(v, u)$$$ по всем парам вершин $$$v$$$ и $$$u$$$ таким, что $$$v < u$$$.

Примеры
Входные данные
3
1 2 1
1 3 2
Выходные данные
4
Входные данные
3
1 2 2
1 3 2
Выходные данные
2
Входные данные
5
1 4 4
1 2 3
3 4 4
4 5 5
Выходные данные
14
Входные данные
2
2 1 1
Выходные данные
1
Входные данные
10
10 2 3
3 8 8
4 8 9
5 8 5
3 10 7
7 8 2
5 6 6
9 3 4
1 6 3
Выходные данные
120