快要过年了，我们打印了很多贺卡去公交站点发给乘客。我们请了许多学生过来发贺卡。每个学生志愿者都得到一个的公共汽车站，他或她将留在那里一整天,邀请人们参与。
这里的公交系统是非常特殊的：共有 n 个站点和 m 个线路，所有的线路都是单向的，连接两个站点。公共汽车离开起始点，到达目的地之后又空车返回起始点。
学生每天早上从总部所在的 1 号站点出发，乘公交车到一个预定的站点邀请乘客。每个站点都被安排了一名学生。在一天结束的时候，所有的学生都回到总部。现在需要知道的是，学生所需的公交费用的总和最小是多少。
输入的第一行是两个整数，代表站点个数 n 和线路条数 m。
第 2 到第 (m + 1) 行，每行三个整数 u, v, w，代表存在一条从 u 出发到达 v 的线路，费用为 w。
输出一行一个整数，表示最小费用。
4 6 1 2 10 2 1 60 1 3 20 3 4 10 2 4 5 4 1 50
210
对于 100\% 的数据，保证：
40\%数据： 1 \leq n, m \leq 10^2。
100\%数据： 1 \leq n, m \leq 10^6。
- 1 \leq n, m \leq 10^6。
- 1 \leq u, v \leq n，1 \leq w \leq 10^9。
- 从 1 出发可以到达所有的站点。