Đất nước Delta là quốc đảo lớn trên thế giới. Đất nước gồm N đảo nhỏ được đánh số từ 1 đến N. Việc đi lại giữa các đảo là rất khó khăn. Vì kinh tế còn rất kém phát triển, nhà nước phải khó khăn lắm mới mở được N – 1 tuyến phà biển để người dân người dân có thể đi lại được giữa hai đảo bất kì. Cách đây không lâu, đất nước mới nhận được sự đầu tư lớn của các nước tư bản. Nhà vua quyết định xây mới K cây cầu để thay cho K tuyến phà. Các cây cầu mới được xây dựng sẽ nối liền hai đảo mà trước đây có tuyến phà nối trực tiếp. Nhà vua muốn tính toán để chọn K tuyến phà nào để xây thành cầu sau cho tổng thời gian để đi lại giữa mọi cặp đỉnh là nhỏ nhất. Tức là: đạt giá trị nhỏ nhất. Trong đo T_{A B} là thời gian đi từ đảo A đến đảo B. Bạn hãy giúp nhà Vua tính toán chọn ra K trong số N - 1 tuyến phà để thay thế bằng cầu.

Input

• Dòng thứ nhất ghi 4 số nguyên N, K, V_P, V_C trong đó V_P là vận tốc nếu đi bằng phà và V_C là vận tốc nếu đi bằng cầu. V_P và V_C có đơn vị là m/s
• N – 1 dòng tiếp theo, mỗi dòng ghi 3 số U V L thể hiện giữa đảo U và đảo V đã có một tuyến phà, và khoảng cách giữa U và V là L mét.

Output

In ra K số là số hiệu của tuyến phà cần được thay thế bằng cầu.

Giới hạn

• 1 ≤ K < N ≤ 10 000
• 1 ≤ V_P, V_C ≤ 100 000
• 1 ≤ L_{U V} ≤ 10⁶
• Thời gian: 1s/test

Example

Input:
6 2 1 2
1 2 5
3 2 6
1 4 4
4 6 4
4 5 5

Output:
1 3