Description

$lmh$刚来到山师学习，他知道以后自己要在这里生活很长时间，所以想要尽快弄清楚学校里面各种设施的位置，方便以后找路。但是他又不希望总是走回头路，希望能够走最少的路（相同的路径只记录一次答案）来将所有的要了解的位置都认一遍，请已经熟知学校路的你为他规划一个路径，让他可以尽快融入山师。（出发的起点与终点不固定）

Format

Input

第一行有两个数$n$和$m$，$n$表示有$n$个需要去探索的地点，$m$表示有$m$条道路。接下来的$m$行，每行形如$“a b c”$用来表示一条道路，意思是地点$a$到地点$b$需要走的路长度为$c$。$（1 \leq n \leq 100,1 \leq m \leq 300，1 \leq a,b \leq n，1 \leq c \leq 10000）$

Output

输出走遍学校共走了多长的路。

Samples

6 9
2 4 11
3 5 13
4 6 3
5 6 4
2 3 6
4 5 7
1 2 1
3 4 9
1 3 2

19