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 \leq 10^5; m \leq 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 \leq a,b \leq n; 1 \leq c \leq 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