Bạn được cho một cây, trong đó mỗi cạnh có một trọng số là số nguyên không âm.

Gọi $d(u, v)$ là trọng số cạnh lớn nhất trên đường đi đơn duy nhất giữa hai đỉnh $u$ và $v$.

Hãy tìm giá trị lớn nhất của $\sum_{i=2}^{n} 2^{d(p_{i-1}, p_i)}$ trong tất cả các hoán vị của các đỉnh $p_1, p_2, \dots, p_n$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ($2 \le n \le 100\,000$): số lượng đỉnh trong cây.

Mỗi dòng trong $n-1$ dòng tiếp theo chứa ba số nguyên $u, v, w$ ($1 \le u, v \le n, 0 \le w \le 30$), biểu thị một cạnh trong cây nối giữa hai đỉnh $u, v$ với trọng số $w$.

Dữ liệu ra

In ra một số nguyên duy nhất: giá trị lớn nhất của $\sum_{i=2}^{n} 2^{d(p_{i-1}, p_i)}$.

Ví dụ

Dữ liệu vào 1

5
1 2 0
2 3 0
3 4 0
4 5 1

Dữ liệu ra 1

6

Ghi chú

Trong ví dụ đầu tiên, một trong những hoán vị tối ưu là $\{4, 5, 3, 2, 1\}$.

Dữ liệu vào 2

10
2 1 1
3 1 1
1 4 0
5 1 2
6 4 1
2 7 2
8 4 2
8 9 3
6 10 0

Dữ liệu ra 2

42