Thành phố Alpha có n đầu mút giao thông và m đoạn đường hai chiều, mỗi đoạn kết nối hai đầu mút. Các đầu mút được đánh số từ 1 đến n. Mỗi đoạn đường đường có độ dài là một số nguyên dương. Trong những giờ cao điểm các đoạn đường có mật độ giao thông tăng chóng mặt. Do đó, để đánh giá khả năng tìm đường thay thế tránh mỗi đoạn đường (x, y), Ban giải pháp chống tắc nghẽn của thành phố mới đưa vào một đại lượng gọi là giá trị thay thế r_x,y được tính bởi công thức sau:

với

• f(u, v, x, y) là độ dài đường đi ngắn nhất từ u đến v khi mà đoạn (x, y) bị nghẽn không di chuyển qua được.
• g(u, v) là độ dài đường đi ngắn nhất từ u đến v mà không có đoạn đường nào bị nghẽn. Đặt r_xy = −1 nếu không có đường đi nào giữa hai đầu mút u, v bất kỳ khi đoạn (x, y) bị nghẽn. Nhắc lại độ dài đường đi từ u đến v là tổng tất cả độ dài các đoạn đường trên đường đi đó.

Yêu cầu: Hãy tìm đoạn đường có giá trị thay thế lớn nhất.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên n, m
• Dòng thứ i^th trong số m dòng tiếp theo chứa ba số nguyên dương x_i , y_i , d_i ,(1 ≤ x_i , yi < n, d_i ≤ 10⁶ với i = 1, 2, ..., m) mô tả một đoạn đường hai chiều có các đầu mút x_ⁱ và y_i với khoảng cách d_i .

Kết quả

Ghi ra trên một dòng duy nhất giá trị r_max tìm được với sai số nhỏ hơn 10⁻⁶.