Increasing Training Load
Increasing training load (ITL in short) is the name of the specific cross-country cycling event
which is organised annually by the Cross-Country Biking Association of Northern Europe.
ITL lasts for a few days and its main rule is that on each day the participants travel
longer distance than on the previous day.
There is a number of specialized biking hotels scattered around the country
and each day the participants travel directly
from some hotel to another one. They do not stop at other hotels during the day.
This year the organizing committee expects many famous international champions to take part in the event.
The committe is certain that they will meet the participants' demand
if they make the total length of ITL as long as possible.
The total length of ITL is just the sum of distances traveled during ITL.
There are some limiting factors which the committee has to consider.
First of all, the obvious consequence of the main ITL rule is the fact that no connection
between two hotels, called a track, can be traveled twice during the event.
On the other hand, the participants may be accomodated in any hotel more than once durring the event.
Fortunately for the committee, each two hotels are connected by at most one track,
which makes the commitee's deliberations somewhat easier.
ITL starts in one of the hotels and ends also in a hotel, it is not important whether
it is the same hotel or two different hotels.
The duration in days of ITL is not limited.
Each track may be traveled in any direction and the length of each track is known to the committee.
Image 1. Example of the hotels and the tracks layout together with the track lengths. The ITL with maximum total length, which is 26, is specified by the green arrows, it starts in hotel 2 and ends in hotel 7. |
The task
You are given the list of all tracks together with their lengths. Find the maximum total length of ITL.
Input
The input contains more text lines. The first line contains two integers N, M separated by space.
N represents the number of hotels, M represents the number of tracks. We suppose the hotels to be labeled by integers
0, 1, 2, ... N−1.
Next, there are M lines, each one specifies one track.
The line contains three integers x, y, w separated by space.
Values x and y represent the labels of the hotels at both ends of the track,
value w represents the length of the track.
The value of N does not exceed 10^{3}, the value of M does not exceed 10^{5}. All track lengths do not exceed 30000.
Output
The otuput contains one text line with single integer representing the maximum possible total length of ITL organized using the tracks and hotels specified by the input data.
Example 1
Input9 12 6 2 10 3 2 6 1 2 1 6 5 8 0 3 9 0 1 5 4 3 7 5 1 12 7 6 3 8 4 4 7 3 11 8 7 2Output
26The scheme of the input and the layout of the maximum possible total length ITL are depicted in the Image 1.
Example 2Input5 8 4 0 9 4 1 6 2 3 8 2 0 4 3 4 7 0 1 1 3 1 4 2 1 2Output 25 |
Image 2. The hotels and the tracks layout together with the track lengths specified in Example 2. The ITL with maximum total length, which is 25, is specified by the green arrow, it starts in hotel 3 and ends in hotel 2. |
Example 3Input8 8 2 1 2 5 4 11 5 6 6 7 0 2 6 7 7 0 1 14 4 3 4 3 2 12Output 17 |
Image 3. The hotels and the tracks layout together with the track lengths specified in Example 3. The ITL with maximum total length, which is 17, is specified by the green arrows, it starts in hotel 6 and ends in hotel 4. |
Public data
The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set