Điều tra chuyến bay

Để chuẩn bị cho buổi trình diễn thời trang, FullHouse Dev được giao nhiệm vụ lập kế hoạch di chuyển cho các người mẫu từ thành phố Syrjälä đến Lehmälä bằng máy bay. Với kinh nghiệm trong việc tối ưu hóa, họ cần tìm ra câu trả lời cho các câu hỏi sau:

• chi phí tối thiểu cho một hành trình?
• có bao nhiêu hành trình có chi phí tối thiểu? (theo modulo \(10^9+7\))
• số chuyến bay ít nhất trong một hành trình có chi phí tối thiểu?
• số chuyến bay nhiều nhất trong một hành trình có chi phí tối thiểu?

INPUT FORMAT:

• 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. Các thành phố được đánh số từ \(1,2,\ldots,n\). Thành phố 1 là Syrjälä, và thành phố \(n\) là Lehmälä.
• \(m\) dòng tiếp theo mô tả các chuyến bay. Mỗi dòng có ba số nguyên \(a\), \(b\), và \(c\): có một chuyến bay từ thành phố \(a\) đến thành phố \(b\) với giá \(c\). Tất cả các chuyến bay đều một chiều.
• Luôn tồn tại ít nhất một hành trình từ Syrjälä đến Lehmälä.

OUTPUT FORMAT:

In ra bốn số nguyên theo thứ tự yêu cầu trong đề bài.

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\)

Ví dụ

INPUT

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

OUTPUT

5 2 1 2

Giải thích

• Chi phí tối thiểu là 5 (có thể đi trực tiếp từ 1 đến 4)
• Có 2 hành trình với chi phí tối thiểu: 1→4 và 1→2→4
• Số chuyến bay ít nhất trong hành trình chi phí tối thiểu là 1 (đi trực tiếp 1→4)
• Số chuyến bay nhiều nhất trong hành trình chi phí tối thiểu là 2 (đi 1→2→4)