Chặn đường

Có $N$ nút và $M$ cạnh vô hướng có trọng số. Bạn cần đi từ nút $1$ đến nút $N$ theo đường đi ngắn nhất.

Một kẻ phá hoại có thể chọn đúng một cạnh và nhân đôi trọng số của cạnh đó, nhằm tối đa hóa độ dài đường đi ngắn nhất từ $1$ đến $N$. Hãy tính mức tăng tối đa có thể xảy ra.

Dữ liệu vào

• Dòng 1: Hai số nguyên $N$ và $M$.
• $M$ dòng tiếp theo: Mỗi dòng gồm ba số nguyên $A$, $B$, $L$ — cạnh nối nút $A$ và $B$ với trọng số $L$.

Dữ liệu ra

Một số nguyên — mức tăng tối đa của đường đi ngắn nhất sau khi kẻ phá hoại chọn cạnh tối ưu.

Ràng buộc

• $1\le N\le 250$
• $1\le M\le 25000$
• $1\le L\le {10}^6$
• Đồ thị liên thông; không có nhiều cạnh giữa cùng một cặp nút.

Ví dụ