Mô tả bài toán: Tìm các thông tin về chuyến bay

Bạn muốn bay từ Syrjälä đến Lehmälä và cần trả lời các câu hỏi sau:

1. Giá tối thiểu của hành trình này là bao nhiêu?
2. Có bao nhiêu hành trình có giá tối thiểu? (kết quả được tính theo modulo ~10^9 + 7~)
3. Số lượng chuyến bay tối thiểu trong hành trình có giá tối thiểu?
4. Số lượng chuyến bay tối đa trong hành trình có giá tối thiểu?

Input:

• Dòng đầu tiên chứa hai số nguyên n và m: số lượng thành phố và số lượng chuyến bay.
• Sau đó, có m dòng, mỗi dòng chứa ba số nguyên a, b, và c:
  • ~a~: thành phố bắt đầu.
  • ~b~: thành phố đích.
  • ~c~: giá của chuyến bay từ ~a~ đến ~b~.

Bạn có thể giả định rằng luôn tồn tại ít nhất một hành trình từ Syrjälä (thành phố 1) đến Lehmälä (thành phố ~n~).

Output:

• In ra bốn số nguyên trên cùng 1 dòng:
  • Giá tối thiểu của hành trình.
  • Số lượng hành trình có giá tối thiểu (mod ~10^9 + 7~).
  • Số lượng chuyến bay tối thiểu trong hành trình có giá tối thiểu.
  • Số lượng chuyến bay tối đa trong hành trình có giá tối thiểu.

Ràng buộc:

• ~1 \leq n \leq 10^5~
• ~1 \leq m \leq 2 \cdot 10^5~
• ~1 \leq a, b \leq n~
• ~1 \leq c \leq 10^9~

Input:

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

Output:

5 2 1 2