Cứu hỏa (cuuhoa.*)

Đội phòng cháy chữa cháy AS làm nhiệm vụ chữa cháy, hoả hoạn cho tất cả các địa điểm trong thành phố \(X\). Với phương châm “Tốc độ cứu hộ, quyết định tất cả”, họ phải xây dựng sẵn lộ trình đến các vị trí để khi cần là sẵn sàng lên đường. Khi có một đám cháy xảy ra tại một khu vực nhất định (\(\mathbf{D}\)), xe cứu hỏa cần được cử đi từ vị trí S. Mỗi con đường giữa các khu vực/trạm cứu hỏa có một thời gian di chuyển nhất định.

Để đảm bảo hiệu quả chữa cháy tối đa, hãy:

• Xác định thời gian di chuyển ngắn nhất để xe cứu hỏa đến được khu vực cháy \(D\).

• Đếm số lượng các tuyến đường khác nhau có cùng thời gian di chuyển ngắn nhất đó. Việc này cực kỳ quan trọng để đội cứu hỏa có các phương án dự phòng nhanh chóng nếu một tuyến đường chính bị tắc nghẽn hoặc không thể đi qua do sự cố bất ngờ.

Dữ liệu vào:

• Dòng 1: Bốn số nguyên \(N,\ M,\ S,\ D\).

  • \(N\): Tổng số địa điểm cần cứu hộ, được đánh số từ 1 đến \(N\).

  • \(M\): Số lượng tuyến đường kết nối các địa điểm.

  • \(S\): vị trí xuất phát

  • \(D\): vị trí xảy ra đám cháy

• \(M\) dòng tiếp theo: Mỗi dòng gồm ba số nguyên \(U,\ V,\ W\).

  • \(U,\ V\): Hai địa điểm được kết nối bởi một tuyến đường.

  • \(W\): Thời gian di chuyển (trọng số) giữa \(U\) và \(V\).

Kết quả:

• Dòng 1: In ra thời gian di chuyển ngắn nhất từ trạm cứu hỏa \(S\) đến khu vực cháy \(D\).

• Dòng 2: In ra số lượng các tuyến đường khác nhau có cùng thời gian di chuyển ngắn nhất đó.

• Nếu không có đường đi từ \(S\) đến \(D\), in ra -1 trên cả hai dòng

Input	Output
6 8 1 6 1 2 5 1 3 10 2 4 10 3 4 5 3 5 15 4 5 5 4 6 10 5 6 5	25 4

Ràng buộc:

• \(1\ \leq \ N\ \leq \ 10^{3}\)

• \(1\ \leq \ S,\ D\ \leq \ N\)

• \(1\ \leq \ M\ \leq \ N \times (N - 1)/2\)

• \(1\ \leq \ W\ \leq \ 10^{9}\)