There are n contests going to be held in the upcoming year.
However, the committee keeps debating whether the contest is of TC (Thinking Creatively) style or CF (Coding Fast) style.

The committee knows in advance that there are m contestants who take part in *exactly two* contests.
The i-th contestant will join the -th contest and then the -th contest.
Note that contests are held in parallel so that there may exist two contestants i and j where .

If the i-th contestant takes a TC-style contest then a CF-style contest,
he or she will feel points of unhappiness. Otherwise he will not feel unhappy.
Therefore, the committee will decides the types of contests according to the following 3 rules:

* There are at least 3 TC-style contests, and the first contest (1-st) should be TC-style.
* There are also at least 3 CF-style contests, and the last contest (n-th) should be CF-style.
* The total unhappiness of contestants is minimized.

The input contains at most 30 sets. For each set:
The first line contains 2 integers n, m ().
The i-th of the following m lines contains 3 integers  ().

For each set, an integer denotes the minimum of total unhappiness.

6 5
1 6 100
1 3 1
1 4 1
2 3 1
2 4 1

100

6 12
2 3 1
2 4 1
2 5 1
3 2 1
3 4 1
3 5 1
4 2 1
4 3 1
4 5 1
5 2 1
5 3 1
5 4 1

4