该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

给定n个地点（编号1，2，……，n），以及地点之间的m条单行道长度。刚开始你在地点1，现在要你从起点分别到其他地点来回往返一次，求最少需要走多长的路。

按要求求出最短需要走多少路。

Input Format

输入数据第一行为地点数n(n<=10000)和路径数m。接下去每行包含i，j，k三个数字，表示地点i到地点j有一条长度为k的单行道。

Output Format

 输出一个数字，表示最短所需要走的路。

4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50

210

Hint

★样例说明

       去地点2往返路为：1->2->4->1最短，走65

       去地点3往返路为：1->3->4->1最短，走80

       去地点4往返路为：1->2->4->1最短，走65

       65+80+65=210

★数据范围

       50%数据n<=100

       80%数据n<=1000

       100%数据n<=10000

m<=2*n