Mỗi buổi sáng khi thức giấc, thầy quản sinh luôn đi bộ từ nhà mình đến ký túc xá (KTX) nhà trường để đánh thức các em học sinh dậy chuẩn bị cho việc đi học. Từ nhà đến KTX có N vị trí được nối với nhau bởi M con đường hai chiều. Mỗi con đường có độ dài xác định. Nhà của thầy giáo quản sinh ở vị trí 1 còn khu (KTX) ở vị trí N. Không có hai vị trí nào được nối với nhau bởi nhiều hơn một con đường và hệ thống đường đi này đảm bảo sự đi lại giữa hai vị trí bất kỳ. Thầy giáo luôn đi trên các con đường này và khi đi, thầy luôn chọn cho mình hành trình ngắn nhất (tổng độ dài các con đường đi qua là nhỏ nhất).
Các học sinh nghịch ngợm không muốn bị đánh thức sớm nên chúng quyết định kéo dài hành trình của thầy giáo trong mỗi buổi sáng bằng cách xây dựng các chướng ngại vật trên đúng một con đường trong số các con đường đã có sao cho việc đi trên con đường này (do phải vòng qua các chướng ngại vật) sẽ có độ dài gấp đôi độ dài ban đầu của nó.
Hãy giúp các học trò nghịch ngợm chọn ra một con đường để xây các chướng ngại vật sao cho hành trình đi đến KTX của thầy giáo là dài nhất có thể.

Input

Dòng đầu ghi hai số nguyên dương N,M (1≤N≤100,1≤M≤10000)
M dòng tiếp theo, dòng thứ i mô tả một con đường gồm 3 số \(A_i\),\(B_i\),\(L_i\) thể hiện có một con đường nối \(A_i\) với \(B_i\) có độ dài \(L_i\) (1≤\(A_i\),\(B_i\)≤n,1≤\(L_i\)≤\(10^6\)).

Output

• Độ tăng lớn nhất hành trình của thầy giáo sau khi các học sinh xây dựng các chướng ngại vật trên một con đường.

5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2

2

Giải thích:

Hành trình ban đầu của thầy giáo là 1-3-4-5 có tổng độ dài là 1+3+2=6.
Sau khi tăng độ dài đường 3-4 lên gấp đôi (từ 3 thành 6) thì hành trình của thầy là 1-3-5 có độ dài 1+7=8. So với độ dài lúc đầu thì tăng 8-6=2