题目描述

有一个邮递员要送东西，邮局在节点 $\red 1$

他总共要送 $\red {N-1}$ 样东西，其目的地分别是 $\red {2 \sim N}$

由于这个城市的交通比较繁忙，因此所有的道路都是单行的

共有 $\red M$ 条道路，通过每条道 路需要一定的时间

这个邮递员每次只能带一样东西

求送完这 $\red {N-1}$ 样东西最少需要多少时 间

输入格式

输入文件第一行包含一个正整数 $\red N$ 和 $\red M$

满足 $\red {N≤1000，M≤100000}$

接下来 $\red M$ 行，每行三个正整数 $\red U$,$\red V$,$\red W$，表示该条道路为 $\red {U->V}$，且通过这条道路需要 $\red W$ 的时间

满足 $\red {1≤U,V≤N，1≤W≤10000}$

输入保证任意两点都能互相到达

输出格式

输出最少需要的时间

样例

输入样例

5 10
2 3 5 
1 5 5 
3 5 6 
1 2 8 
1 3 8 
5 3 4
4 1 8 
4 5 3 
3 5 6 
5 4 2

输出样例

83