Mỗi buổi sáng, FJ thức dậy và đi qua trang trại từ nhà đến chuồng. Trang trại gồm \(N\) cánh đồng (\(1 \le N \le 250\)) được nối với nhau bởi \(M\) con đường hai chiều (\(1 \le M \le 25\,000\)), mỗi con đường có một độ dài tương ứng. Nhà của FJ nằm ở cánh đồng \(1\), còn chuồng nằm ở cánh đồng \(N\). Không có cặp cánh đồng nào được nối bởi nhiều con đường trùng lặp, và có thể di chuyển giữa hai cánh đồng bất kỳ trong trang trại bằng cách đi theo một dãy đường thích hợp. Khi đi từ cánh đồng này đến cánh đồng khác, FJ luôn chọn một lộ trình gồm một dãy đường có tổng độ dài nhỏ nhất.

Những cô bò của Farmer John, vẫn luôn thích gây rắc rối, quyết định cản trở thói quen buổi sáng của ông. Chúng dự định chất một đống kiện cỏ khô trên đúng một trong \(M\) con đường của trang trại, khiến độ dài của con đường đó tăng gấp đôi. Những cô bò muốn chọn con đường để chặn sao cho mức tăng quãng đường từ nhà đến chuồng của FJ là lớn nhất. Hãy giúp chúng xác định có thể làm lộ trình của FJ dài thêm nhiều nhất bao nhiêu.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) cách nhau bởi một dấu cách.
• \(M\) dòng tiếp theo, dòng thứ \(j\) chứa ba số nguyên \(A_j\), \(B_j\) và \(L_j\) cách nhau bởi dấu cách, mô tả con đường hai chiều thứ \(j\). Trong đó, \(A_j\) và \(B_j\) là các chỉ số từ \(1\) đến \(N\) của hai cánh đồng được nối bởi con đường, còn \(L_j\) là độ dài con đường, nằm trong đoạn từ \(1\) đến \(1\,000\,000\).

Ràng buộc

• \(1 \le N \le 250\).
• \(1 \le M \le 25\,000\).
• \(1 \le A_j,B_j \le N\).
• \(1 \le L_j \le 1\,000\,000\).
• Không có hai con đường cùng nối một cặp cánh đồng, và mọi cặp cánh đồng đều có thể đi đến nhau.

Dữ liệu ra

In ra mức tăng lớn nhất có thể của tổng độ dài lộ trình ngắn nhất của FJ khi tăng gấp đôi độ dài của một con đường duy nhất.

Ví dụ

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

2

Nguồn

USACO 2014 February Contest, Gold — Roadblock

Tác giả: Brian Dean.