Giải bài trực tuyến

Công ty MCA là một công ty vận tải nổi tiếng tại đất nước Peace, với mạng lưới hoạt động trong khắp cả nước. Sắp đến kỷ niệm 30 năm thành lập, giám đốc công ty quyết định mở một đợt khuyến mãi lớn cho tất cả các khách hàng. Cụ thể là công ty sẽ mở một số tuyến đường vận chuyển miễn phí cho khách hàng.

Mỗi tuyến đường như vậy sẽ xuất phát từ một thành phố, qua một số thành phố (không đi qua thành phố nào 2 lần) rồi quay về nơi xuất phát. Nếu tính chi phí vận chuyển trung bình trên từng tuyến đường thì chi phí chi ra cho đợt khuyến mãi này sẽ không nhỏ nên giám đốc cũng muốn các tuyến đường này thỏa điều kiện tổng độ dài đường đi chia cho tổng số con đường trong tuyến đường đó (gọi là chi phí của tuyết đường) là nhỏ nhất.

Cho một mạng lưới vận chuyển hàng của công ty MCA hãy tìm ra tuyến đường thích hợp nhất (thỏa cả 2 điều kiện trên) cho đợt khuyến mãi. Xuất ra chi phí của tuyến đường tìm được.

Input

Dòng đầu tiên ghi hai số nguyên N và M là số thành phố và số con đường trong mạng lưới. ( 1 ≤ N ≤ 100, 1 ≤ M ≤ 9000 )

M dòng tiếp theo, mỗi dòng ghi ba số nguyên a b c với ý nghĩa có đường đi một chiều từ a đến b với độ dài là c. ( 1 ≤ c ≤ 2²³ )

Output

Gồm 1 dòng duy nhất ghi một số thập phân với là chi phí nhỏ nhất. Nếu không tồn tại tuyến đường nào thỏa mãn ghi ra -1. ( ghi chính xác đến 2 chữ số sau dấu phẩy )

Example

Input:
3 3
1 2 1
2 3 1
3 1 1

Output:
1.00