Có \(N\) trạm cung cấp dịch vụ truyền thông được đánh số từ \(1\) đến \(N\). Giữa các trạm có \(M\) đường nối để truyền thông tin hai chiều. Hệ thống được coi là bình ổn nếu hai trạm bất kỳ có thể trao đổi thông tin cho nhau.

Sau một sự cố thiên nhiên, một số đoạn cáp bị hỏng, trong đó có \(D\) đoạn cáp thường và có \(R\) đoạn cáp đặc biệt mà chi phí sửa chữa chúng sẽ tốn kém hơn nhiều so với những đoạn cáp còn lại.

Yêu cầu

• Sau sự cố, hệ thống còn bình ổn hay không? Nếu không, hãy đưa ra phương án khắc phục tiết kiệm nhất: tổng chiều dài các đoạn cáp cần sửa chữa là nhỏ nhất, và hạn chế tối đa việc thay các đường cáp đặc biệt (chỉ thay khi không còn cách nào khác).

Dữ liệu vào

• Dòng đầu ghi \(4\) số nguyên: \(N, M, D, R\) (với \(N \le 200, 0 \le M, D \le 10^4, D + R \le M\)).
• Dòng thứ \(i\) trong \(M\) dòng tiếp theo ghi thông tin về đoạn cáp \(i\), mỗi dòng ghi \(3\) số nguyên \(u, v, c\), với \(c\) là chiều dài đoạn cáp nối giữa trạm \(u\) và \(v\) \((1 \le c \le 1000)\).
• Nếu \(D \gt 0\), thì dòng thứ \(M + 2\) của tệp ghi \(D\) số, mỗi số là số hiệu của mỗi đoạn cáp bị hỏng. Nếu \(D = 0\), thì dòng này ghi số \(0\).
• Nếu \(R \gt 0\), thì dòng \(M+3\) của tệp sẽ ghi \(R\) số, là số hiệu của các đoạn cáp đặc biệt bị hỏng. Nếu \(R = 0\), thì dòng này ghi số \(0\).
• (Các số cách nhau ít nhất \(1\) khoảng trắng, và danh sách cáp thường và cáp đặc biệt bị hư là hoàn toàn phân biệt.)

Dữ liệu ra

• Một số nguyên là tổng chiều dài nhỏ nhất tìm được (ghi số \(0\) nếu hệ thống vẫn bình ổn).

Input 1

5 10 1 7
5 3 2
4 5 9
4 2 4
4 3 1
2 3 1
1 4 5
1 5 4
1 2 7
2 5 8
1 3 8
3
9 6 2 8 4 10 7

Output 1

8