EIU Programming Practices and Exams

Nhu cầu điện ngày càng cao khiến các các đường dây truyền tải bị quá tải. Một mạng lưới có thể được xem là một cây với các hộ gia đình là các nút lá. Mỗi dây có khả năng chịu tải cố định, nếu công suất tiêu thụ của các gia đình trong nhánh đó vượt quá khả năng chịu tải thì toàn bộ nhánh đó sẽ mất điện. Một nhánh được xem là không có nguy cơ mất điện nếu chịu tải của dây lớn hơn ít nhất 10% so với công suất tiêu thụ điện của các hộ gia đình trong nhánh. Biết công suất tiêu thụ điện của các hộ gia đình, hãy cho biết những hộ nào có thể bị mất điện nếu các đường dây không được nâng cấp sớm.

Input

Dòng đầu tiên là số node trên mạng điện N và chỉ số của trạm điện R. Các node trên mạng điện được đánh số từ 0 đến N – 1.

N – 1 dòng tiếp theo, mỗi dòng gồm 3 số nguyên a, b, c thể hiện dây nối giữa a và b có khả năng chịu tải là c (0 < c < 10⁶)

Các dòng còn lại, mỗi dòng gồm hai số nguyên a, w thể hiện hộ gia đình a có công suất tiêu thụ là w (0 < w < 10⁶)

Output

Xuất ra chỉ số của các hộ gia đình có nguy cơ bị mất điện trên 1 dòng. Dữ liệu xuất ra theo thứ tự tăng dần phân cách bởi khoảng trắng.

Example

Input:
7 0
0 1 21
0 2 10
2 5 8
1 3 21
1 4 13
3 6 11
6 11
4 9
5 7 	


Output:
4 6