Chặn Đường (Gold)

Có $N$ địa điểm được nối với nhau bởi $M$ con đường hai chiều. Mỗi con đường nối hai địa điểm $A$ và $B$ với độ dài $L$. Một người đi từ địa điểm $1$ đến địa điểm $N$ theo đường đi ngắn nhất.

Một nhóm muốn cản trở việc di chuyển này bằng cách chặn một con đường — làm đôi độ dài của nó (nhân đôi). Nhóm sẽ chọn con đường để tối đa hóa mức tăng của đường đi ngắn nhất từ $1$ đến $N$.

Hãy tính mức tăng lớn nhất có thể đạt được.

Dữ liệu vào

• Dòng 1: Hai số nguyên $N$ và $M$ ($1\le N\le 250$, $1\le M\le 25000$).
• $M$ dòng tiếp theo: Mỗi dòng gồm ba số nguyên $A$, $B$, $L$ — con đường nối địa điểm $A$ và $B$ có độ dài $L$ ($1\le L\le {10}^6$).

Đồ thị liên thông, không có cạnh trùng lặp.

Dữ liệu ra

Một số nguyên duy nhất: mức tăng lớn nhất của đường đi ngắn nhất sau khi nhân đôi một con đường.

Ràng buộc

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

Ví dụ