• Nhưng "thiên tài không bằng thiên tai". Một đợt suy thoái diện rộng bất ngờ ập đến khiến toàn bộ thuật toán đầu tư của Pitomon đổ vỡ. Mất trắng cơ đồ, Pitomon bị dồn vào bước đường cùng. Trong cơn tuyệt vọng và phẫn nộ, Pitomon quyết định "chơi bẩn" - nhắm thẳng vào mạng lưới an ninh của Ngân hàng Trung ương.
• Mạng lưới an ninh của vương quốc là một đồ thị dạng cây gồm \(N\) máy chủ và \(N-1\) cáp quang nối giữa chúng. Mỗi sợi cáp quang nối giữa hai máy chủ \(u\) và \(v\) được gắn một mã khóa bảo mật \(W\). Cơ quan tình báo định nghĩa "Độ an toàn" của đường truyền giữa hai máy chủ \(X\) và \(Y\) được tính bằng phép toán thao tác bit XOR (Tuyển loại) của tất cả các mã khóa bảo mật trên đường đi ngắn nhất từ \(X\) đến \(Y\).
• Biết được dữ liệu bảo mật truyền qua các máy chủ trên mạng lưới cáp quang, Pitomon đã sử dụng kỹ năng thao tác bit để tìm ra cặp máy chủ có "lỗ hổng XOR" lớn nhất. Lỗ hổng này chính là chìa khóa để Pitomon hack thành công, tuồn vô hạn tiền ảo về tài khoản của mình. Một nhóm Hacker của Pitomon đang muốn tìm ra một cặp máy chủ \((X, Y)\) bất kỳ trong mạng lưới sao cho "Độ an toàn" giữa chúng là lớn nhất để tiến hành thử nghiệm xâm nhập. Hãy giúp Pitomon tính giá trị "Độ an toàn" lớn nhất đó.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) mô tả số lượng máy chủ trong mạng lưới ngân hàng.
• \(N-1\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên \(u, v, W\) biểu diễn một cáp quang nối giữa máy chủ \(u\) và máy chủ \(v\) mang mã khóa bảo mật \(W\).

Output

• Một dòng duy nhất chứa 1 số nguyên là giá trị "Độ an toàn" lớn nhất tìm được giữa một cặp máy chủ bất kỳ trong mạng lưới.

Scoring

• Subtask 1 : có 20% số điểm với \(N \le 1000\) và \(W \le 10^9\)
• Subtask 2 : có 30% số điểm với \(N \le 10^5\); cấu trúc mạng lưới cáp quang có dạng một đường thẳng
• Subtask 3 : có 50% số điểm với \(N \le 10^5\) và \(W \le 10^{12}\)

Sample Input 1

4
1 2 2
1 3 4
2 4 8

Sample Output 1

14

Sample Input 2

5
1 2 5
2 3 9
3 4 2
4 5 7

Sample Output 2

14

Giải thích

Ở ví dụ thứ nhất, Pitomon chọn cặp máy chủ là (3, 4). Đường đi ngắn nhất từ máy chủ 3 đến máy chủ 4 sẽ đi qua các máy chủ: 3 -> 1 -> 2 -> 4. 
Các mã khóa bảo mật trên đường đi lần lượt là 4, 2 và 8. Giá trị độ an toàn = 4 XOR 2 XOR 8 = 14. Đây là mức độ an toàn lớn nhất có thể đạt được.

Ở ví dụ thứ hai (mạng lưới dạng đường thẳng), Pitomon chọn cặp máy chủ là (1, 4). Đường đi ngắn nhất từ máy chủ 1 đến máy chủ 4 sẽ đi qua các máy chủ: 1 -> 2 -> 3 -> 4. 
Các mã khóa bảo mật trên đường đi lần lượt là 5, 9 và 2. Giá trị độ an toàn = 5 XOR 9 XOR 2 = 14.