Chặn Đường

Cho đồ thị vô hướng $N$ đỉnh, $M$ cạnh có trọng số. Một người đi từ đỉnh $1$ đến đỉnh $N$ theo đường đi ngắn nhất.

Bạn được phép nhân đôi trọng số của đúng một cạnh. Hãy tìm cạnh tốt nhất để nhân đôi sao cho đường đi ngắn nhất mới tăng nhiều nhất so với ban đầu.

In ra độ tăng tối đa.

Dữ liệu vào

• Dòng 1: Hai số nguyên $N$ và $M$
• $M$ dòng tiếp theo: Ba số nguyên $A_i,B_i,L_i$ — cạnh nối $A_i$ với $B_i$ có trọng số $L_i$

Dữ liệu ra

• In ra độ tăng tối đa của đường đi ngắn nhất.

Ràng buộc

• $1\le N\le 250$
• $1\le M\le 25000$
• $1\le L_i\le {10}^6$

Ví dụ