Bạn dự định đi từ Syrjälä đến Lehmälä bằng máy bay. Hãy trả lời các câu hỏi sau:

• Giá rẻ nhất của một lộ trình như vậy là bao nhiêu?
• Có bao nhiêu lộ trình với giá rẻ nhất? (chia lấy dư cho \(10^9 + 7\))
• Số lượng chuyến bay tối thiểu của một lộ trình với giá rẻ nhất là bao nhiêu?
• Số lượng chuyến bay tối đa của một lộ trình với giá rẻ nhất là bao nhiêu?

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số lượng thành phố và chuyến bay.
  Các thành phố được đánh số \(1, 2, \ldots, n\). Thành phố \(1\) là Syrjälä, và thành phố \(n\) là Lehmälä.
• Sau đó có \(m\) dòng, mỗi dòng gồm ba số nguyên \(a, b, c\): có một chuyến bay một chiều từ \(a\) đến \(b\) với giá \(c\).
• Bảo đảm tồn tại ít nhất một lộ trình từ Syrjälä đến Lehmälä.

Output

• In ra bốn số nguyên theo thứ tự:
  (1) giá rẻ nhất,
  (2) số lộ trình có giá rẻ nhất (mod \(10^9+7\)),
  (3) số chuyến bay tối thiểu trong số các lộ trình rẻ nhất,
  (4) số chuyến bay tối đa trong số các lộ trình rẻ nhất.

Constraints

• \(1 \le n \le 10^5\)
• \(1 \le m \le 2 \cdot 10^5\)
• \(1 \le a, b \le n\)
• \(1 \le c \le 10^9\)

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

5 2 1 2