Bơm rủ bạn gái đi chơi lễ hội hoa hồng nhân ngày 8/3. Lễ hội được sắp đặt trong một bản đồ gồm \(n\) địa điểm đánh số từ \(1\) tới \(n\) và \(n-1\) con đường đánh số từ \(1\) tới \(n-1\). Con đường thứ \(i\) nối giữa hai địa điểm \(u_i\) và \(v_i\) và cho phép di chuyển giữa hai địa điểm này theo cả hai chiều. Hệ thống đường đi đảm bảo sự đi lại giữa hai địa điểm bất kỳ.

Bơm muốn chọn một hành trình giữa hai địa điểm của lễ hội mà không đi qua con đường nào hai lần. Ngoài ra vì e ngại hành trình có thể khá dài nên Bơm muốn chọn một địa điểm làm nơi nghỉ chân không trùng với nơi bắt đầu và kết thúc hành trình.

Trên mỗi con đường có thể trưng bày một trong hai loại hoa: hồng đỏ hoặc hồng xanh. Bạn gái của Bơm lại yêu cầu một hành trình thỏa mãn: số con đường trưng bày hồng đỏ phải bằng số con đường trưng bày hồng xanh trên phần hành trình từ nơi bắt đầu tới điểm nghỉ chân cũng như trên phần hành trình từ điểm nghỉ chân tới điểm kết thúc.

Yêu cầu

Hãy cho biết có bao nhiêu hành trình thỏa mãn cả yêu cầu của Bơm và bạn gái. Một hành trình là một cặp điểm \((s,t)\) trong đó \(s < t\) cho biết hành trình đó đi từ địa điểm \(s\) tới địa điểm \(t\). Hai hành trình có điểm bắt đầu và kết thúc giống nhau được coi là giống nhau cho dù cách chọn nơi nghỉ chân trên hai cách đi có thể khác nhau.

Input

• Dòng đầu chứa số nguyên dương \(n \leq 10^5\)
• \(n-1\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(u_i, v_i, c_i\) cho biết có con đường nối giữa \(u_i\) và \(v_i\) và trên con đường đó trưng bày loại hoa \(c_i\). \(c_i \in \{0,1\}\), \(c_i = 0\) ứng với loại hoa hồng đỏ và \(c_i = 1\) ứng với loại hoa hồng xanh

Output

• Ghi ra một số nguyên duy nhất là số hành trình thỏa mãn cả yêu cầu của Bơm và bạn gái

Example

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

1