With Guild elections around the corner, PCS has decided last minute to form its very own Guild party - Programming Competition Party (PCP). They have decided to focus on just a single policy because quality is always better than quantity. PCP promises to optimise the layout of the UWA campus so the minimal total length of path is needed to connect every single building on campus. Although this may actually increase the distance students walk to get to their classes, PCP believes it is a higher priority to save money from path maintenance rather than being on time to class.

To really impress voters, PCP has decided to show off an algorithm which will demonstrate how they will actually implement this promised policy. However they are delegating the task of designing the algorithm to our most beloved PCS member, you (yes, you reading this!!).

Can you design an algorithm that's fast enough to solve all example University layouts in time?

Note: It is guaranteed that there exists a sequence of connected paths between any two buildings for any given University layout.

Input Specification

A single line with two space-separated integers \(B(1\le B\le 5000)\), the number of buildings on campus, and \(P(B-1\le P\le \frac{B(B-1)}{2})\), the number of existing paths connecting buildings.

Then P more lines with three space-separated integers \(u(1\le u\le B)\), \(v(1\le v\le B)\) and \(w(1\le w\le 20)\), representing that there exists a path between building number \(u\) and building number \(v\) with length \(w\).

Output Specification

The minimal total length of path to keep that still connects all buildings.

Sample Case 1

Input

3 3
0 1 1
0 2 3
1 2 5

Output

4

Sample Case 2

Input

5 6
0 1 1
0 2 5
0 3 3
1 2 6
1 4 7
3 4 7

Output

16