Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

QBTRANS - Vận chuyển hàng

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/qbtrans


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 ≤ 223 )

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


Được gửi lên bởi:special_one
Ngày:2008-12-10
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Ioicamp - Marathon 06 - 07

hide comments
2020-08-18 13:12:42
luồng AC
2019-12-04 04:01:36
Nhật hào dơ vl
2019-05-13 09:25:31
sao ít người làm vậy
2015-08-05 08:14:16 Prismatic
=)) Cái chia không cẩn thận bị lỗi ngay :3
update: test yếu :v

Last edit: 2015-08-06 12:05:04
2014-02-04 09:23:45 Hướng Thái Dương




Last edit: 2014-02-04 11:22:46
2014-02-04 09:23:45 Hướng Thái Dương
ẹc cạnh trùng nhau nữa cơ á ừa ừa :3
2011-07-19 17:11:46 trandatbav
Qua bua
2011-07-12 14:16:27 Erik
luu y, co the co canh trung nhau
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.