Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game.

There are cities on the map and road plans. Each road plan consists of the following:

• Two cities which can be directly connected by a road.
• The length of the proposed road.

The entire road plan is designed in such a way that if one builds all the roads, it will be possible to travel between any pair of cities.

A ticket enables you to travel between two different cities. There are tickets, and each ticket has a cost associated with it. A ticket is considered to be useful if there is a path between those cities.

Simon wants to choose two cities, and , and build a minimal number of roads so that they form a simple path between them. Let be the sum of costs of all useful tickets and be the sum of lengths of all the roads Simon builds. The profit for pair is defined as . Note that and are not necessarily unique and may be the same cities.

Given road plans and ticket prices, help Simon by printing the value of his maximum possible profit on a new line.