Cho dữ liệu mô tả cây, hãy viết chương trình tìm đỉnh có chỉ số nhỏ nhất làm gốc và thỏa mãn các điều kiện sau:

• Đỉnh gốc có đúng ~2~ nhánh con, mỗi nhánh có ít nhất một node.
• Gọi ~TW_1~ là tổng trọng số của nhánh con thứ nhất, ~TW_2~ là tổng trọng số của nhánh con thứ hai, thì ~|TW_1 – TW_2|~ có giá trị nhỏ nhất.

Input

• Dòng đầu tiên là số node của cây ~N~ ~(0 < N ≤ 10^5)~. Các node được đánh số từ ~1~ đến ~N~.
• Dòng tiếp theo chứa ~N~ số nguyên ~w_i~ ~(0 < w_i ≤ 10^9)~, là trọng số của node thứ ~i~.
• Dòng thứ ~i~ trong ~N-1~ dòng tiếp theo gồm ~2~ số nguyên ~u_i~, ~v_i~ cho biết có cạnh nối ~u_i~ và ~v_i~

Note: ~80\%~ Testcases có ~N~ không vượt quá ~1000~

Output

• In ra chỉ số của đỉnh gốc và tổng trọng số của hai nhánh con theo thứ tự tăng dần. Nếu không tồn tại đỉnh gốc, in ra -1.

Example Input

4
2 3 1 4
1 2
1 3
2 4

Example Output

2 3 4