Thuyền trưởng Sinbad có dự định đưa đoàn tàu cùng thủy thủ đoàn đi trao đổi hàng hóa vòng quanh các hòn đảo. Sinbad quyết định sẽ xuất phát tại một hòn đảo bất kì, sau đó đi qua một số hòn đảo và quay trở về hòn đảo xuất phát ( một hòn đảo có thể được thăm nhiều lần). Là một thuyền trưởng tài ba và đầy kinh nghiệm, Sinbad muốn chọn một lộ trình sao cho lợi nhuận thu được là tối đa. Lợi nhuận thu được đối với một hành trình được tính dựa trên thương số giữa tổng lượng hàng hóa bán được dọc theo hành trình và tổng độ dài hành trình. Cho biết bản đồ của vùng biển gồm N hòn đảo được đánh số từ 1 đến N và M tuyến hải trình giữa chúng cùng lượng hàng hóa dự kiến bán được c[i,j] nếu đi từ đảo i đến đảo j (c[i,j]=c[j,i]) (các tuyến hải trình xem như hai chiều). Bạn hãy giúp Sinbad lập lộ trình tối ưu cho các thủy thủ đoàn
Dữ liệu vào: từ file profit.inp gồm :
- Dòng đầu tiên gồm 2 số n,m (1<=n<=100) lần lượt là số đảo và số hải trình giữa chúng
- M dòng tiếp theo, mỗi dòng gồm 4 số nguyên A,B,C,D (1<=A,B<=N; 1<=C,D<=255) cho biết tồn tại hải trình giữa hai hòn đảo A, B trong đó C là số hàng hóa dự kiến bán được và D là độ dài của hải trình.
Dữ liệu ra: ghi lên file profit.out gồm một số thực P duy nhất là lợi nhuận tối đa ứng với phương án tối ưu tìm được (yêu cầu lấy chính xác 3 chữ số sau dấu phẩy)
Ví dụ:
profit.inp
5 6
1 4 172 100
4 5 184 100
5 1 252 100
1 2 12 100
3 1 6 100
2 3 10 100
profit.out
2.520