Mỗi buổi sáng, nông dân John (FJ) thức dậy và đi băng qua nông trại từ nhà ông ta tới chuồng bò. Nông trại là sự kết hợp của cánh đồng được nối bởi đường đi hai chiều , mỗi con đường có một độ dài nhất định. Nhà của FJ ở cánh đồng thứ , và chuồng bò ở cánh đồng thứ . Không có hai cánh đồng nào có nhiều đường đi với nhau, và có thể đi lại giữa hai cánh đồng bất kì trong nông trại bằng cách đi bộ theo một dãy các đường đi. Khi đi từ một cánh đồng này sang cánh đồng khác, FJ luôn chọn một cách đi chứa một dãy các đường đi cho tổng độ dài của đường đi là nhỏ nhất.
Những con bò của FJ không tốt như mọi khi và đã quyết định can thiệp vào công việc thường xuyên của FJ vào mỗi buổi sáng. Chúng dự định xây một đống kiện hàng đúng trên một trong đường đi trên nông trại, làm tăng gấp đôi chiều dài của nó (do FJ phải trèo qua đống kiện hàng khi đi trên đường này). Đàn bò mong muốn chọn một đường đi để chặn lại sao cho khoảng cách từ nhà của FJ tới chuồng bò tăng tối đa. Hãy giúp đàn bò tính toán xem chúng có thể tăng bao nhiêu đơn vị độ dài của cách đi của FJ.
Dữ liệu:
Dòng đầu ghi hai số nguyên dương ;
dòng tiếp theo, dòng thứ gồm ba số nguyên mô tả một con đường hai chiều nối với và có chiều dài .
Kết quả:
Ghi ra độ dài lớn nhất tối đa có thể tăng được của cách đi ngắn nhất của FJ bởi nhân đôi độ dài của một con đường.
Ví dụ:
Dữ liệu:
5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2
Kết quả:
2
Giải thích:
Nếu đàn bò nhân đôi độ dài của đường đi từ cánh đồng thứ đến cánh đồng thứ , khi đó cách đi ngắn nhất của FJ là , có tổng độ dài là , lớn hơn hai đơn vị so với cách đi ngắn nhất trước.
