B'Berland is a large country with developed airlines. In total, there are n cities in the country that are historically served by the Berlaflot airline. The airline operates bi-directional flights between m pairs of cities, i -th of them connects cities with numbers a_i and b_i and has a price c_i for a flight in both directions. It is known that Berlaflot flights can be used to get from any city to any other (possibly with transfers), and the cost of any route that consists of several consequent flights is equal to the cost of the most expensive of them. More formally, the cost of the route from a city t_1 to a city t_k with (k-2) transfers using cities t_2, t_3, t_4, ldots, t_{k - 1} is equal to the maximum cost of flights from t_1 to t_2 , from t_2 to t_3 , from t_3 to t_4 and so on until the flight from t_{k - 1} to t_k . Of course, all these flights must be operated by Berlaflot. A new airline, S8 Airlines, has recently started operating in Berland. This airline provides bi-directional flights between all pairs of cities that are not connected by Berlaflot direct flights. Thus, between each pair of cities there is a flight of either Berlaflot or S8 Airlines. The cost of S8 Airlines flights is calculated as follows: for each pair of cities x and y that is connected by a S8 Airlines flight, the cost of this flight is equal to the minimum cost of the route between the cities x and y at Berlaflot according to the pricing described earlier. It is known that with the help of S8 Airlines flights you can get from any city to any other with possible transfers, and, similarly to Berlaflot, the cost of a route between any two cities that consists of several S8 Airlines flights is equal to the cost of the most expensive flight. Due to the increased competition with S8 Airlines, Berlaflot decided to introduce an air reform and change t'...