Xét đồ thị có hướng có trọng số và hàm trọng số . Mỗi cạnh có trọng số là , đặt . Một dãy là một chu trình trong khi và chỉ khi và đều thuộc , khi đó được gọi là độ dài của chu trình . Đồng thời đặt , và định nghĩa giá trị trung bình của chu trình là:
Tức là trung bình cộng trọng số của tất cả các cạnh trên .
Đặt là giá trị trung bình nhỏ nhất của tất cả các chu trình trong . Mục tiêu hiện tại là: Cho trước đồ thị và trọng số , hãy tìm giá trị trung bình nhỏ nhất của tất cả các chu trình trong , tức là .
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên dương và , cách nhau bởi dấu cách, trong đó , lần lượt biểu thị số đỉnh và số cạnh của đồ thị.
dòng tiếp theo, mỗi dòng chứa ba số cách nhau bởi dấu cách, biểu thị có một cạnh với trọng số .
Dữ liệu đảm bảo đồ thị liên thông, tồn tại chu trình và có một điểm có thể đi đến tất cả các điểm khác.
Kết quả:
Chỉ chứa một số thực , yêu cầu xuất chính xác đến 8 chữ số thập phân.
