Tom sống ở thành phố XYZ, hàng ngày Tom thường chọn đường đi ngắn nhất từ nhà tới trường và từ trường về nhà. Thành phố XYZ mà Tom ở có n nút giao thông được đánh số từ 1 đến n. Nhà Tom nằm ở nút giao thông 1 còn trường học của Tom nằm ở nút giao thông n. Từ nút giao thông i đến nút j có không quá một đường đi một chiều độ dài ~d_{ij}~, tất nhiên, có thể có đường đi một chiều khác đi từ nút j đến nút i. Trong thời gian tới, thành phố sẽ tổ chức nhiều sự kiện văn hóa và

Tom biết rằng, khi đi làm từ nhà đến cơ quan thì có p nút sẽ bị ùn tắc là ~a_1~,~a_2~,..,~a_p~, còn khi đi từ trường về nhà thì có q nút sẽ bị ùn tắc là ~b_1~,~b_2~,..,~b_q~. Tom băn khoăn muốn biết độ dài đường ngắn nhất đi từ nhà đến trường mà không đi qua các nút ~a_1~,~a_2~,..,~a_p~ và độ dài đường ngắn nhất đi từ trường về nhà mà không đi qua các nút ~b_1~,~b_2~,..,~b_q~ là bao nhiêu?

Ví dụ, thành phố có 5 nút giao thông và các đường đi một chiều với độ dài tương ứng như hình bên. Giả sử nút 4 là nút bị ùn tắc khi đi từ nhà đến trường, nút 2 và nút 4 là nút bị ùn tắc khi đi từ trường về nhà, khi đó độ dài đường đi ngắn nhất từ nhà đến trường là 19 (đường đi 1->2->3->5, không đi qua nút 4), độ dài đường đi ngắn nhất từ trường về nhà là 17 (đường đi 5->3->1, không đi qua nút 2 và nút 4)

Yêu cầu: Cho biết các đường đi một chiều với độ dài tương ứng mô tả hệ thống giao thông thành phố XYZ và các nút sẽ bị ùn tắc ~a_1~,~a_2~,..,~a_p~, ~b_1~,~b_2~,..,~b_q~. Hãy tìm độ dài đường đường đi ngắn nhất để đi từ nhà (nút giao thông 1) đến trường (nút giao thông n) mà không đi qua các nút ~a_1~,~a_2~,..,~a_p~ và từ trường về nhà mà không qua các nút ~b_1~,~b_2~,..,~b_q~.

Dữ liệu vào:

• Dòng đầu ghi bốn số nguyên dương ~n,m,p,q~ (3 ≤ ~n~ ≤ 10000, ~m~ ≤ ~10^5~, 1 ≤ ~p, q~ ≤ ~n-2~)
• Dòng thứ hai ghi ~p~ số nguyên ~a_1~,~a_2~,..,~a_p~ (1 < ~a_i~ < ~n~)
• Dòng thứ ba ghi ~q~ số nguyên ~b_1~,~b_2~,..,~b_q~ (1 < ~b_i~ < ~n~)
• m dòng tiếp theo, mỗi dòng 3 số nguyên ~i,j~, ~d_{ij}~ (1 ≤ ~i,j~ ≤ ~n~, 0 < ~d_{ij}~ ≤ 30000) mô tả có đường đi một chiều từ i đến j có độ dài ~d_{ij}~.

Hai số liên tiếp trên một dòng cách nhau một dấu cách. Dữ liệu bảo đảm luôn có nghiệm.

Kết quả: Gồm một dòng chứa 2 số nguyên cách nhau một dấu cách, số thứ nhất là độ dài đường đi ngắn nhất từ nhà đến trường, số thứ hai là độ dài ngắn nhất từ trường về nhà thỏa mãn điều kiện đã nêu.

Ví dụ:

INPUT:

5 11 1 2
4
2 4
1 2 10
1 4 3
2 3 6
2 5 10
3 1 12
3 4 6
3 5 3
4 1 5
4 3 5
5 3 5
5 4 10

OUTPUT

19 17

Chú ý: 50% số test có n≤100