eolymp
bolt
Try our new interface for solving problems
Problems

Flowery Trails

Flowery Trails

Time limit 1 second
Memory limit 128 MiB

In order to attract more visitors, the manager of a national park had the idea of planting flowers along both sides of the popular trails, which are the trails used by common people. Common people only go from the park entrance to its highest peak, where views are breathtaking, by a shortest path. So, he wants to know how many metres of flowers are needed to materialize his idea.

For instance, in the park whose map is depicted in the figure, common people make only one of the three following paths (which are the shortest paths from the entrance to the highest peak).

  • At the entrance, some start in the rightmost trail to reach the point of interest 3 (after 100 metres), follow directly to point 7~(200 metres) and then pick the direct trail to the highest peak (620 metres).

  • The others go to the left at the entrance and reach point 1 (after 580 metres). Then, they take one of the two trails that lead to point 4 (both have 90 metres). At point 4, they follow the direct trail to the highest peak (250 metres).

Notice that popular trails (i.e., the trails followed by common people) are highlighted in yellow. Since the sum of their lengths is 1930 metres, the extent of flowers needed to cover both sides of the popular trails is 3860 metres (3860 = 2 \cdot 1930).

Given a description of the park, with its points of interest and (two-way) trails, the goal is to find out the extent of flowers needed to cover both sides of the popular trails. It is guaranteed that, for the given inputs, there is some path from the park entrance to the highest peak.

Input data

The first line has two integers: p~(2 \le p \le 10000) and t~(1 \le t \le 250000). p is the number of points of interest and t is the number of trails. Points are identified by integers, ranging from 0 to p - 1. The entrance point is 0 and the highest peak is point p - 1.

Each of the following t lines characterises a different trail. It contains three integers, p_1, p_2, and l~(1 \le l \le 1000), which indicate that the (two-way) trail links directly points p_1 and p_2 (not necessarily distinct) and has length l (in metres).

Output data

The output has a single line with the extent of flowers (in metres) needed to cover both sides of the popular trails.

Examples

Input example #1
10 15
0 1 580
1 4 90
1 4 90
4 9 250
4 2 510
2 7 600
7 3 200
3 3 380
3 0 150
0 3 100
7 8 500
7 9 620
9 6 510
6 5 145
5 9 160
Output example #1
3860
Input example #2
4 7
0 1 1
0 2 2
0 3 10
0 3 3
1 3 2
2 3 1
1 1 1
Output example #2
18
Source 2014 ACM Southwestern Europe Regional Contest (SWERC), Problem B