Olympic Tin học Sinh Viên

Có N thành phố và M đường hàng không hai chiều giữa một số cặp thành phố nào đó, các đường bay được quản lý bởi 16 hãng hàng không. Các thành phố được đánh số từ 1 tới N (N ≤ 100) và các hãng được đánh số từ 1 tới 16.

Được biết chi phí bay trực tiếp giữa hai thành phố i, j bất kỳ (nếu như có đường bay ) là C. Nếu đang đi máy bay của một hãng đến sân bay nào đó rồi chuyển sang máy bay của hãng khác thì sẽ phải mất thêm một khoản phụ phí A.

Yêu cầu: Cho trước hai thành phố S và F, hãy tìm hành trình bay từ thành phố S đến thành phố F với chi phí ít nhất. Với giả thiết rằng luôn luôn tồn tại cách bay từ S tới F.

Input

• Dòng 1 ghi sáu số nguyên dương N, M, C, A, S, F. (1 ≤ A, C ≤ 100)
• M dòng tiếp theo, mỗi dòng có dạng u v k₁ k₂ ... cho biết rằng giữa thành phố u và thành phố v có đường bay và k₁, k₂, ... là số hiệu các hãng sở hữu đường bay đó

Output

Ghi chi phí tối thiểu phải trả

Example

Input:
15 16 3 2 1 5
1 2 1
2 3 1
3 4 1 2
3 9 2
4 9 1
5 10 1 3
6 7 1
6 11 1
7 8 1
7 13 2
8 9 1
10 15 3
11 12 1
12 13 1
13 14 1 3
14 15 1 3

Output:
37

Giải thích: Cần đi từ thành phố 1 đến thành phố 5. Chi phí đường bay trực tiếp giữa hai thành phố bất kỳ C = 3, 
phụ phí chuyển tuyến A = 2. Các số ghi bên cạnh các đường bay trực tiếp là tên các hãng sở hữu đường bay đó.

Minh họa: