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
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à
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
Dữ liệu vào:
- Dòng đầu ghi bốn số nguyên dương
(3 ≤ ≤ 10000, ≤ , 1 ≤ ≤ ) - Dòng thứ hai ghi
số nguyên , ,.., (1 < < ) - Dòng thứ ba ghi
số nguyên , ,.., (1 < < ) - m dòng tiếp theo, mỗi dòng 3 số nguyên
, (1 ≤ ≤ , 0 < ≤ 30000) mô tả có đường đi một chiều từ i đến j có độ dài .
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
Comments