Đường đi rẻ nhất, ít chặng nhất

Bối cảnh và bài toán

Một hệ thống định tuyến ưu tiên trước hết tổng chi phí thấp nhất; nếu có nhiều tuyến cùng chi phí, tuyến có ít cạnh hơn được ưu tiên.

Yêu cầu

Tìm cặp (chi phí tối thiểu, số cạnh ít nhất trong các đường có chi phí tối thiểu) từ s tới t.

Input

Dòng đầu n, m, s, t; tiếp theo m cạnh có hướng u, v, w.

Output

In hai số cost edges, hoặc -1 nếu không thể tới t.

Ràng buộc

• 2 <= n <= 2*10^5
• 0 <= m <= 3*10^5
• 0 <= w <= 10^9 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 200, m <= 500 (nếu có m) | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

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

Output

5 2

Giải thích. Trạng thái được so theo (tổng chi phí, số cạnh), nên tiêu chí phụ chỉ dùng khi chi phí bằng nhau.

Ví dụ 2

Input

3 1 1 3
1 2 1

Output

-1

Giải thích. Trạng thái được so theo (tổng chi phí, số cạnh), nên tiêu chí phụ chỉ dùng khi chi phí bằng nhau.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from CSES Investigation. Bản FULLHOUSE DEV đã biên tập lại bối cảnh/format theo phạm vi khóa học.