XTREEW

Cây là một đơn đồ thị vô hướng liên thông không có chu trình. Giữa hai đỉnh \(x\), \(y\) trên cây, luôn luôn tồn tại và duy nhất một đường đi đơn giữa chúng.

Cho một cây với các cạnh có trọng số không âm. Ta gọi khoảng cách giữa hai đỉnh là tổng xor (hay tổng nim) của các trọng số các cạnh trên đường đi đơn giữa hai đỉnh đó. Lưu ý là cặp \((x, y)\) và \((y, x)\) được coi là một cặp

Yêu cầu: Hãy tính tổng khoảng cách của tất cả các cặp đỉnh trên cây.

Input

• Dòng đầu ghi số nút của cây: \(n\)

• \(n - 1\) dòng tiếp theo, mỗi dòng ghi một cạnh của cây: \(u, v, L (1 ≤ u, v ≤ n)\)

Output

In ra một số nguyên là kết quả bài toán

Example

7
1 2 3
1 3 2
2 4 1
2 5 1
3 6 2
3 7 3

34

Scoring

• Trong tất cả các test: \(1 ≤ n ≤ 10^5 , 0 ≤ L ≤ 10^9\)

• Có \(20\%\) số test với \(n ≤ 5000\)

• Có \(30\%\) số test với mỗi đỉnh đều kề với nhiều nhất 2 đỉnh khác

• Có \(50\%\) số test với ràng buộc gốc