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

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