Một thành phố bao gồm các giao lộ và các con đường nối giữa chúng. Tuyết phủ kín thành phố, vì vậy thị trưởng lập một danh sách các con đường cần được dọn tuyết sao cho:

• Số lượng con đường được chọn là ít nhất có thể.
• Mọi cặp giao lộ vẫn liên thông với nhau, tức là giữa hai giao lộ bất kỳ chỉ tồn tại đúng một đường đi.

Đội dọn tuyết chỉ có một máy dọn tuyết và một tài xế. Máy bắt đầu tại giao lộ ~S~.

Máy dọn tuyết tiêu thụ 1 lít nhiên liệu cho mỗi mét di chuyển, kể cả khi đi qua một con đường đã được dọn trước đó. Máy phải dọn sạch tất cả các con đường trong danh sách theo một thứ tự nào đó sao cho tổng lượng nhiên liệu tiêu thụ là nhỏ nhất.

Sau khi hoàn thành, máy sẽ dừng lại tại giao lộ cuối cùng mà nó đi tới.

Yêu cầu

Hãy tính lượng nhiên liệu tối thiểu mà máy dọn tuyết cần sử dụng.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~S~, lần lượt là số giao lộ của thành phố và giao lộ xuất phát của máy dọn tuyết.
• ~N - 1~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~A~, ~B~, ~C~, cho biết có một con đường nối trực tiếp giữa hai giao lộ ~A~ và ~B~ với độ dài ~C~ mét.

Dữ liệu ra

In ra một số nguyên duy nhất là lượng nhiên liệu tối thiểu cần sử dụng để dọn sạch tất cả các con đường.

Ràng buộc

• ~1 <= N <= 100000~
• ~1 <= S <= N~
• ~1 <= A, B <= N~
• ~1 <= C <= 1000~

Input

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

Output

7