Orta məsafə
Ölkənin yol şəbəkəsi haqqında məlumat verilmişdir. Sizin vəzifəniz, iki şəhər arasında ən qısa yolun orta uzunluğunu hesablamaqdır.
Orta uzunluq, bütün şəhər cütləri (a, b) üçün şəhər a-dan şəhər b-yə olan ən qısa yolların uzunluqlarının l_a_{, b} cəminin, belə cütlərin sayına olan nisbəti kimi müəyyən edilir. Burada a və b - 1 ilə N arasında olan fərqli təbii ədədlərdir və N ölkədəki ümumi şəhər sayını göstərir. Yalnız aralarında ən qısa yol olan şəhər cütlərini nəzərə almalısınız.
Giriş verilənləri
Yol şəbəkəsi giriş faylında aşağıdakı kimi təqdim edilir: birinci sətir N və K (1 ≤ N ≤ 100, 1 ≤ K ≤ N(N − 1)) ədədlərini ehtiva edir, burada K yolların sayını göstərir. Sonrakı K sətirin hər biri tək istiqamətli yolun təsvirini ehtiva edir - üç tam ədəd a_i, b_i və l_i (1 ≤ a_i, b_i ≤ N, 1 ≤ l_i ≤ 1000). Bu, a_i şəhərindən b_i şəhərinə l_i uzunluğunda bir yolun olduğunu bildirir.
Çıxış verilənləri
Çıxış faylında tək bir həqiqi ədəd - şəhərlər arasındakı orta məsafəni çıxarmalısınız. Məsafə 6 ondalık rəqəmlə göstərilməlidir.