You are given a description of the country's road network. Your task is to find the average length of the shortest path between two cities Average length is the ratio of the sum over all pairs of cities (\textbf{a}, \textbf{b}) the lengths of shortest paths \textbf{l_a}_\{, b\} of the city in \textbf{a} city \textbf{b} to the number of such pairs. Here \textbf{a} and \textbf{b} - a variety of natural numbers from \textbf{1} to \textbf{N}, where \textbf{N} - total number of cities in the country. Should consider only those pairs of cities, among which is the shortest path. \InputFile The road network is given in the input file as follows: The first line contains the numbers \textbf{N} and \textbf{K} (\textbf{1} ≤ \textbf{N} ≤ \textbf{100}, \textbf{1} ≤ \textbf{K} ≤ \textbf{N(N − 1)}), where \textbf{K} - number of roads. Each of the following \textbf{K} lines contains the description of one-way road - three integers \textbf{a_i}, \textbf{b_i} and \textbf{l_i} (\textbf{1} ≤ \textbf{a_i}, \textbf{b_i} ≤ \textbf{N}, \textbf{1} ≤ \textbf{l_i} ≤ \textbf{1000}). This means that there is a path of length \textbf{l_i}, which leads out of town \textbf{a_i} to the city \textbf{b_i}. \OutputFile You must bring to the output file a unique real number of the average distance between cities. Distance must be inferred from \textbf{6} characters after the decimal point.