No submission language available for this problem.

题目背景

在一个美丽而神秘的岛屿上，生活着一个和平而友善的部落。这个部落以他们精湛的渔业技巧而闻名，他们擅长捕捞各种美味的海鲜。

然而，由于岛屿的偏远位置和海洋资源的有限性，部落的美味海鲜无法被更多的人品尝到，无法得到更广泛的认可和销售。为了解决这个问题，一个名叫小码君的年轻渔民决定采取行动，将部落的美味海鲜带到世界的餐桌上。

题目描述

小码君决定组织一场精彩的美食展示，以展示部落的渔业技巧和美味海鲜。为了吸引更多的食客和潜在买家，他决定在不同城市的餐厅设立展示摊位，并邀请学生志愿者来帮助他们推广和销售海鲜，学生志愿者通过公共交通方式去每一个不同城市,然后晚上回到岛屿。因此小码君需要计算出学生志愿者们需要支付的最小总交通费用，以便在有限的预算内完成展示摊位的设置和海鲜的运输。

公共交通系统是比较特殊的：共有 $n$ 个站点和 $m$ 个线路，所有的线路都是单向的，连接两个站点，每条线路都有交通费用。岛屿是 $1$ 号站点。

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

210

提示

数据规模与约定

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

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