题目背景

在电视时代，没有多少人观看戏剧表演。Malidinesia 古董喜剧演员意识到这一事实，他们想宣传剧院，尤其是古色古香的喜剧片。

题目描述

他们已经打印了请帖和所有必要的信息和计划。许多学生被雇来分发这些请柬。每个学生志愿者被指定一个确切的公共汽车站，他或她将留在那里一整天，邀请人们参与。

这里的公交系统是非常特殊的：共有 $n$ 个站点和 $m$ 个线路，所有的线路都是单向的，连接两个站点。公共汽车离开起始点，到达目的地之后又空车返回起始点。

学生每天早上从总部所在的 $1$ 号站点出发，乘公交车到一个预定的站点邀请乘客。每个站点都被安排了一名学生。在一天结束的时候，所有的学生都回到总部。现在需要知道的是，学生所需的公交费用的总和最小是多少。

输入格式

输入的第一行是两个整数，代表站点个数 $n$ 和线路条数 $m$。

第 $2$ 到第 $(m + 1)$ 行，每行三个整数 $u, v, w$，代表存在一条从 $u$ 出发到达 $v$ 的线路，费用为 $w$。

输出格式

输出一行一个整数，表示最小费用。

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \leq n, m \leq 10^6$。
• $1 \leq u, v \leq n$，$1 \leq w \leq 10^9$。
• 从 $1$ 出发可以到达所有的站点。

可见测试数据

输入数据 1

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

输出数据 1

210

输入数据 2

5 11
1 2 14
2 1 15
2 3 20
3 2 1
3 4 12
4 3 15
4 5 18
5 4 18
3 2 24
4 3 24
1 3 17

输出数据 2

218

输入数据 3

6 13
1 2 16
2 1 1
2 3 15
3 2 18
3 4 10
4 3 13
4 5 1
5 4 9
5 6 9
6 5 6
6 2 11
6 3 17
3 2 25

输出数据 3

256