Nhân dịp 8/3, Thuận đã lên kế hoạch mua quà cho bạn gái rất kĩ lưỡng. Trên đường đi tới nhà bạn gái, Thuận sẽ ghé ngang qua một số tiệm hoa, quà, trà sữa, v.v ... để mua những món quà mà cô ấy thích nhất, do đó anh đã cố định một tuyến đường đi. Hệ thống giao thông trong thành phố có thể mô hình hóa thành một đồ thị có \(n\) đỉnh, và \(m\) cạnh hai chiều, có trọng số. Dãy các địa điểm mà Thuận sẽ đi là \(s = s_1, s_2, s_3, \dots, s_k = t\) trong đó \(s\) là nhà Thuận, \(t\) là nhà của bạn gái, và có tổng cộng \(k\) địa điểm trên tuyến đường.
Trên chiếc xe Light (Full-Self Driving, không cần người lái) của Thuận được tích hợp phần mềm định vị VK Map. Thuận đã cung cấp điểm đến là \(t\) cho xe. Khi ở tại vị trí là đỉnh \(x\) bất kì trên đồ thị, VK Map sẽ xác định điểm \(y\) liền kề với \(x\) và thuộc đường đi ngắn nhất từ \(x\) tới \(t\) (cũng như toàn bộ phần còn lại của đường đi ngắn nhất tới \(t\)). Nếu kế tiếp, Thuận lựa chọn đi đến điểm \(z \neq y\), thì VK Map sẽ tính toán lại toàn bộ đường đi.
Là một kỹ sư đã thiết kế nên xe Light, Thuận rất quan tâm tới tốc độ xử lý và hiệu suất của phần mềm VK Map này. Thuận biết rõ, khi tồn tại nhiều đường đi ngắn nhất khác nhau cùng tới được \(t\), phần mềm sẽ gợi ý một tuyến bất kì. Nhưng hôm nay, khác với mọi khi, Thuận đã cố định sẵn lộ trình mà anh ấy sẽ đi là dãy \(s_1, s_2, \dots, s_k\), bất kể gợi ý của hệ thống. Anh ấy tò mò, liệu trong trường hợp tốt nhất, cũng như tệ nhất thì VK Map sẽ tính toán lại đường đi bao nhiêu lần?

Yêu cầu: Cho trước \(n,m,k\); mô tả hạ tầng giao thông của thành phố; tuyến đường Thuận dự định đi. Hỏi số lần tạo đường đi mới ít nhất, và nhiều nhất của VK Map là bao nhiêu?

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((1 \leq n \leq 2 \times 10^{5}, 1 \leq m \leq 4 \times 10^{5})\).
• \(m\) dòng tiếp theo, mõi dòng chứa ba số nguyên \(u, v, w\) \((1 \leq u, v \leq n, 1 \leq w \leq 10^{9})\), thể hiện rằng có một con đường nối hai địa điểm \((u,v)\) với trọng số là \(w\).
• Dòng tiếp theo chứa số nguyên \(k\) \((1 \leq k \leq n)\).
• Dòng cuối cùng chứa \(k\) số nguyên \(s_1, s_2, \dots, s_k\) là chỉ số của \(k\) địa điểm sẽ đi qua

Output

• Ghi ra hai số nguyên là số lần tính toán lộ trình gợi ý tối thiểu và tối đa.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(m,n \le 2000, w = 1\).
• Subtask \(2\) (\(25\%\) số điểm): \(m,n \le 2000\).
• Subtask \(3\) (\(25\%\) số điểm): \(w = 1\).
• Subtask \(4\) (\(25\%\) số điểm): không có ràng buộc gì thêm.

Example

4 4
1 2 1
1 3 2
2 3 1
3 4 1
3
1 3 4

0 1

6 9
1 5 1
5 4 1
1 2 1
2 3 1
3 4 1
4 1 1
2 6 1
6 4 1
4 2 1
4
1 2 3 4

2 2