Sat Dec 22, 2012 10:36 pm
Admin 1782. Xây cầu
Mã bài: BRIDGES
Mã bài: BRIDGES
Đấ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 TA 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, VP, VC trong đó VP là vận tốc nếu đi bằng phà và VC là vận tốc nếu đi bằng cầu. VP và VC 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 ≤ VP, VC ≤ 100 000
1 ≤ LU V ≤ 106
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