Bạn Phương là một hướng dẫn viên du lịch tại đất nước ~X~ có ~N~ thành phố và ~N - 1~ tuyến đường hai chiều, tuyến đường thứ ~i~ có độ dài ~w_i~ nối liền hai thành phố ~u_i~ và ~v_i~. Dữ liệu luôn đảm bảo tồn tại hành trình di chuyển giữa bất kì cặp thành phố nào.

Bạn Phương được chọn một thành phố ~S~ để bắt đầu hành trình, sau đó ghé thăm ~N - 1~ thành phố còn lại, mỗi thành phố đúng một lần, rồi quay trở lại thành phố ~S~ và kết thúc chuyến du lịch. Khi đang ở một thành phố ~u~, bạn Phương có thể thực hiện một trong hai hành động sau:

• Ghé thăm thành phố ~v~ kề với ~u~ thông qua tuyến đường nối hai thành phố đó. Chi phí của hành động này là ~A \cdot w~ với ~w~ là độ dài của tuyến đường.

• Ghé thăm thành phố ~v~ bất kì bằng cách dịch chuyển tức thời đến thành phố đó. Chi phí của hành động này là ~B~.

Yêu cầu: Tính tổng chi phí tối thiểu để thực hiện chuyến du lịch.

Input

Dòng đầu tiên gồm ba số nguyên ~N, A, B~ (~2 \le N \le 200000~; ~1 \le A, B \le 10^9~) – lần lượt là số thành phố và các chi phí để thực hiện hành động.

~N - 1~ dòng tiếp theo gồm các số nguyên ~u_i~, ~v_i~, ~w_i~ (~1 \le u_i, v_i \le N~; ~u_i \neq v_i~; ~1 \le w_i \le 10^9~) – tuyến đường thứ ~i~ nối liền hai thành phố ~u_i~ và ~v_i~, có độ dài là ~w_i~.

Output

Một số nguyên duy nhất là chi phí tối thiểu để thực hiện chuyến du lịch.

Scoring

Sample Input 1

5 9 10
1 4 2
4 5 5
2 5 3
5 3 4

Sample Output 1

50

Sample Input 2

5 2 10
1 4 2
4 5 5
2 5 3
5 3 4

Sample Output 2

38