Vị trí nhà hàng

Hệ thống giao thông của một thành phố gồm $n$ nút giao được nối với nhau bởi $m$ con đường hai chiều. Con đường thứ $i$ nối hai nút giao khác nhau $a_i$, $b_i$ và có độ dài $w_i$. Giữa hai nút giao bất kì có nhiều nhất một con đường, và từ nút giao nào cũng có thể đi tới mọi nút giao khác.

Người ta muốn mở một nhà hàng sao cho việc đi lại tới nhà hàng là thuận tiện nhất. Cụ thể, gọi $D$ là khoảng cách đi theo đường từ nhà hàng tới nút giao xa nhất; hãy chọn vị trí đặt nhà hàng để $D$ nhỏ nhất.

Điểm mấu chốt: nhà hàng không bắt buộc phải nằm ở một nút giao, nó có thể nằm ở một điểm bất kì trên một con đường. Nếu nhà hàng nằm trên con đường nối $a$ và $b$ có độ dài $w$, cách $a$ một khoảng $x$ ($0\le x\le w$), thì khoảng cách từ nhà hàng tới nút giao $v$ bằng $min(x+d(a,v),(w-x)+d(b,v))$, với $d(·,·)$ là khoảng cách ngắn nhất giữa hai nút giao.

Hãy tìm giá trị nhỏ nhất có thể của $D$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$: số nút giao và số con đường.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $a_i$, $b_i$, $w_i$: con đường thứ $i$ nối nút giao $a_i$ với nút giao $b_i$ và có độ dài $w_i$.

Dữ liệu ra

Một số thực duy nhất là giá trị nhỏ nhất của $D$. Kết quả được chấp nhận nếu sai số tuyệt đối hoặc tương đối không vượt quá ${10}^{-6}$.

Ràng buộc

• $2\le n\le 200$
• $n-1\le m\le {\displaystyle \frac{n(n-1)}{2}}$
• $1\le a_i,b_i\le n$, $a_i\ne b_i$
• $1\le w_i\le {10}^5$
• Giữa hai nút giao bất kì có nhiều nhất một con đường, và đồ thị liên thông.

Ví dụ