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.

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

The first line of the input has two integers: n and m. n is the number of points of interest and m is the number of trails. Points are identified by integers, ranging from 1 to n. The entrance point is 1 and the highest peak is point n.

Each of the following m lines characterises a different trail. It contains three integers, u_i, v_i and l_i, which indicate that a (two-way) trail links directly points u_i and v_i (not necessarily distinct) and has length l_i (in metres).

Output

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

Constraints

• 2 \le n \le 10000
• 1 \le m \le 250 000
• 1 \le u_i, v_i \le n
• 1 \le l_i \le 1000

Examples

Input:

4 7
1 2 1
1 3 2
1 4 10
1 4 3
2 4 2
3 4 1
2 2 1

Output:

18

Input:

10 15
1 2 580
2 5 90
2 5 90
5 10 250
5 3 510
3 8 600
8 4 200
4 4 380
4 1 150
1 4 100
8 9 500
8 10 620
10 7 510
7 6 145
6 10 160

Output:

3860