Bạn muốn đi từ Syrjälä (thành phố \(1\)) đến Lehmälä (thành phố \(n\)) bằng máy bay.
Hãy trả lời các câu hỏi sau cho các lộ trình có giá rẻ nhất từ \(1\) đến \(n\):

• Giá rẻ nhất là bao nhiêu?
• Có bao nhiêu lộ trình đạt giá rẻ nhất? (lấy phần dư theo \(10^9+7\))
• Số lượng chuyến bay tối thiểu trong số các lộ trình rẻ nhất là bao nhiêu?
• Số lượng chuyến bay tối đa trong số các lộ trình rẻ nhất là bao nhiêu?

Bạn có thể giả định rằng tồn tại ít nhất một lộ trình từ \(1\) đến \(n\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) — số thành phố và số chuyến bay một chiều (\(1\) là Syrjälä, \(n\) là Lehmälä).
• Mỗi trong \(m\) dòng tiếp theo chứa ba số nguyên \(a, b, c\) mô tả một chuyến bay một chiều từ \(a\) đến \(b\) với giá \(c\).

Output

In ra bốn số nguyên trên một dòng, lần lượt là:

1. Tổng chi phí rẻ nhất từ \(1\) đến \(n\).
2. Số lượng lộ trình đạt chi phí 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