Orta məsafə#1670
Ölkənin yol şəbəkəsinin təsviri verilir. Sizin vəzifəniz iki şəhər arasında ən qısa yolun orta uzunluğunu tapmaqdır.
Orta uzunluq belə təyin olunur: bütün şəhər cütləri üçün ən qısa yolların uzunluqlarının l_{a, b} cəmi cütlərin sayına bölünür. Burada və -dən -ə qədər olan fərqli təbii ədədlərdir, ölkədəki şəhərlərin ümumi sayıdır. Yalnız ən qısa yol mövcud olan şəhər cütlərini nəzərə alın.
Giriş faylında yol şəbəkəsi aşağıdakı kimi verilir: birinci sətirdə və (1 \leq N \leq 100, 1 \leq K \leq N(N-1)) ədədləri verilir, burada yolun sayıdır. Sonrakı sətirin hər birində bir tərs keçidli yol təsvir olunur — üç tam ədəd a_i, b_i və l_i (1 \leq a_i, b_i \leq N, 1 \leq l_i \leq 1000). Bu o deməkdir ki, a_i şəhərindən b_i şəhərinə uzunluğu l_i olan bir yol vardır.
Tək bir real ədəd çıxışa verin — şəhərlər arasındakı orta məsafəni. Cavab onluq vergüldən sonra dəqiqliklə çap olunmalıdır.
Nümunə 1