Có \(n\) thành phố và có \(m\) chuyến bay đi qua lại giữa các thành phố. Hãy khảo sát đường đi từ thành phố \(1\) đến thành phố \(N\) và trả lời các câu hỏi sau:

• Chi phí thấp nhất là bao nhiêu?
• Có bao nhiêu đường đi với chi phí thấp nhất? (mod \(10^9+7\))
• Số lượng chuyến bay ít nhất với chi phí thấp nhất?
• Số lượng chuyến bay nhiều nhất với chi phí thấp nhất?

Input

• Dòng đầu tiên gồm \(2\) số nguyên \(n,m\).
• \(m\) dòng tiếp theo, mỗi dùng gồm \(3\) số nguyên \(u,v,c\), thể hiện chuyến bay từ thành phố \(u\) đến thành phố \(v\) có chi phí là \(c\). Lưu ý, tất cả chuyến bay là 1 chiều.

Output

• Chi phí thấp nhất tìm được.

Điều kiện

• \(1 \le n \le 10^5\)
• \(1 \le m \le 2 \times 10^5\)
• \(1 \le u,v \le n\)
• \(1 \le c \le 10^9\)

Sample Input 1

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

Sample Output 1

5 2 1 2