Cho đồ thị có hướng $n$ đỉnh, $m$ cạnh với các đỉnh được đánh số từ $1$ đến $n$. Mỗi cạnh được gán một trọng số dương - độ dài cùa cạnh. Độ dài của một đường đi bằng tổng độ dài các cạnh trên đường đi đó. Viết chương trình trả lời các câu hỏi sau:

1. Độ dài đường đi ngắn nhất từ đỉnh $1$ đến đỉnh $n$ là bao nhiêu?
2. Có bao nhiêu đường đi ngắn nhất khác nhau từ $1$ đến $n$? (Do con số này có thể rất lớn nên bạn chỉ cần in phần dư của nó khi chia cho ${10}^9+7$)
3. Số cạnh ít nhất trên một đường đi ngắn nhất từ $1$ đến $n$ là bao nhiêu?
4. Số cạnh nhiều nhất trên một đường đi ngắn nhất từ $1$ đến $n$ là bao nhiêu?

Input

• Dòng đầu tiên chứa hai số nguyên dương $n,m(n\le {10}^5;m\le 2\times {10}^5)$
• Tiếp theo là $m$ dòng, mỗi dòng chứa ba số nguyên $u,v,w$ mô tả có một cạnh nối trực tiếp từ $u$ đến $v$ và có độ dài $w(1\le a,b\le n;1\le c\le {10}^9)$

Dữ liệu đảm bảo rằng luôn có đường đi từ đỉnh $1$ đến đỉnh $n$

Output

• In ra bốn số nguyên trên một dòng cách nhau bằng dấu trống (space) lần lượt là câu trả lời cho các câu hỏi 1, 2, 3, 4.

Sample Input

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

Sample Output

5 2 1 2