Thám hiểm hành tinh

Bạn là một nhà thám hiểm vũ trụ, vừa hạ cánh xuống hành tinh Zogron, nơi có nhiều thành phố nổi kết nối với nhau bằng các tuyến đường bay liên hành tinh. Bạn cần di chuyển từ thành phố xuất phát Orbital-1 đến thành phố cuối cùng Orbital-\(n\). Là một nhà du hành thông minh, bạn muốn trả lời những câu hỏi sau trước khi lên đường:

• Chi phí thấp nhất để bay từ Orbital-\(1\) đến Orbital-\(n\) là bao nhiêu?

• Có bao nhiêu lộ trình với chi phí thấp nhất? (Kết quả lấy dư với \(10^9 + 7\))

• Số lượng chuyến bay tối thiểu của một lộ trình có chi phí thấp nhất là bao nhiêu?

• Số lượng chuyến bay tối đa của một lộ trình có chi phí thấp nhất là bao nhiêu?

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số thành phố nổi và số tuyến đường bay (\(1 \leq n \leq 10^5\), \(1 \leq m \leq 2 \cdot 10^5\)).

• M dòng tiếp theo, mỗi dòng mô tả một tuyến đường bay bằng ba số nguyên \(a, b, c\): có một tuyến bay từ Orbital-\(a\) đến Orbital-\(b\) với chi phí \(c\).

• Tất cả các tuyến bay đều là một chiều.

• Đảm bảo luôn có ít nhất một lộ trình từ Orbital-1 đến Orbital-\(n\).

Output

• Dòng đầu tiên in ra chi phí thấp nhất để đi từ Orbital-\(1\) đến Orbital-\(n\).

• Dòng thứ hai in ra số lượng lộ trình có chi phí thấp nhất, lấy dư với \(10^9 + 7\).

• Dòng thứ ba in ra số lượng chuyến bay tối thiểu của một lộ trình có chi phí thấp nhất.

• Dòng thứ tư in ra số lượng chuyến bay tối đa của một lộ trình có chi phí thấp nhất.

Example

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

5 2 1 2