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

Cho đồ thị ~n~ đỉnh có dạng cây ~(~là đồ thị liên thông có đúng ~n - 1~ cạnh~)~. Đặc điểm của đồ thị này là giữa ~2~ đỉnh bất kỳ trên cây sẽ chỉ có đúng ~1~ đường đi duy nhất đến nhau. Bạn được giao cho nhiệm vụ tìm ra đường đi dài nhất giữa ~2~ đỉnh trên cây này.

Input

Dòng đầu là số nguyên ~n~ (~n \le 10^5~).

~N - 1~ dòng sau, mỗi dòng gồm ~3~ số ~u, v, w~ cho biết cạnh nối đỉnh ~u, v~ có độ dài là ~w~ (~w \le 10^9~).

Output

Ghi ra độ dài của đường đi dài nhất.

Sample Input

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

Sample Output

7