Sau khi giành chức vô địch ICPC Regional danh giá, Kiên và Thế quyết định cùng nhau đi du lịch ở đất nước đăng cai tổ chức ICPC World Final Bangladesh trong kỳ nghỉ giáng sinh 2020. Bản đồ hàng không thế giới có thể được biểu diễn bằng một đồ thị có ~n~ đỉnh đánh số từ ~1~ đến ~n~ với ~m~ cạnh hai chiều tương ứng với một đường bay giữa hai quốc gia nào đó. Việt Nam được đánh số thứ tự ~1~ và Bangladesh mang số thứ tự ~n~. Cạnh thứ ~i~ có dạng ~u_i~ , ~v_i~ và ~w_i~ thể hiện một đường bay hai chiều kéo dài ~w_i~ giờ giữa hai quốc gia ~u_i~ và ~v_i~ .

Được biết, trên thế giới có ~k~ loại dưa hấu khác nhau, mỗi quốc gia có thể có một hoặc nhiều hơn loại dưa hấu. Thế là một người đam mê dưa hấu, anh muốn nhân cơ hội được bay vòng quanh thế giới này để mua ít nhất ~l~ ~(l ≤ k)~ loại dưa hấu khác nhau để về tặng gấu Kiên. Ngược lại, Kiên lại không muốn tốn qua nhiều thời gian đi lại và muốn tới đích sớm nhất có thể.

Kiên và Thế đang bận dọn đồ đạc nên muốn nhờ bạn tính số giờ ít nhất để di chuyển từ Việt Nam tới Bangladesh mà vẫn mua được đủ dưa hấu để Thế tặng gấu Kiên.

Dữ liệu

• Dòng đầu tiên gồm bốn số nguyên không âm ~n~ ~(1 ≤ n ≤ 10^5)~, ~m~ ~(1 ≤ m ≤ 10^5)~, ~k~ ~(1 ≤ k ≤ 5)~ và ~l~ ~(0 ≤ l ≤ k)~ biểu diễn số quốc gia trên bản đồ hàng không, số đường bay giữa các quốc gia, số loại dưa hấu khác nhau trên thế giới và số loại dưa hấu Thế muốn mua tặng gấu Kiên.
• Dòng thứ ~i~ trong ~n~ dòng tiếp theo, mỗi dòng bắt đầu với một số nguyên không âm ~s_i~ ~(0 ≤ s_i ≤ k)~ là số loại dưa hấu khác nhau ở đất nước thứ ~i~. Tiếp theo là ~s_i~ số nguyên dương phân biệt ~a_{ij}~ ~(1 ≤ j ≤ s_i, 1 ≤ a_{ij} ≤ k)~ biểu diễn các loại dưa hấu khác nhau ở đất nước này.
• Dòng thứ ~i~ trong ~m~ dòng tiếp theo chứa ba số nguyên dương ~u_i~ ~(1 ≤ u_i ≤ n)~, ~v_i~ ~(1 ≤ v_i ≤ n)~ và w_i ~(1 ≤ w_i ≤ 10^9)~ biểu diễn thông tin của đường bay thứ ~i~.

Kết quả

Gồm một số nguyên dương duy nhất là số giờ ít nhất để đi từ Việt Nam tới Bangladesh với điều kiện mua được ít nhất ~l~ loại dưa hấu khác nhau. Nếu không tồn tại đường đi từ Việt Nam tới Bangladesh để mua đủ dưa hấu trên đường đi, in ra ~−1~.

Sample Input 1

6 6 2 2
0
1 1
0
1 1
1 1
0
1 2 1
2 3 2
1 4 2
4 5 2
5 6 1
3 6 1

Sample Output 1

-1

Sample Input 2

6 6 2 2
0
1 1
0
1 1
1 2
0
1 2 1
2 3 2
1 4 2
4 5 2
5 6 1
3 6 1

Sample Output 2

5

Sample Input 3

6 6 2 2
0
1 1
0
0
1 2
0
1 2 1
2 3 2
1 4 2
4 5 2
5 6 1
3 6 1

Sample Output 3

6

Giới hạn

• Có 20% số điểm có ~1 ≤ n ≤ 10~.
• Có 20% số điểm có ~l = 0~.
• Có 20% số điểm có ~k = 1~.
• Có 20% số điểm có ~1 ≤ n, m ≤ 100~.
• 20% số điểm còn lại không có điều kiện gì thêm.