题号：NC20675
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld
题目描述
MIKU酱是个玩游戏氪金的人，游戏公司给她制定了新的规则，如果想从关卡i到关卡j，你需要交一些钱就可以了，但同时，MIKU酱的爸爸zjw很爱她，所以她可以每过一关就向她爸要一次钱，但她爸每次给他的钱是固定的，MIKU酱是个不会节省的女孩，哪怕每次多出来的钱，她也会拿去买肥宅快乐水，所以每次要的钱一定花完，因为MIKU酱不想挨骂，所以希望每次他爸给她的钱最少。
tips（到达第n关即通过，每到达一关一定能通过这关）
输入描述:
多组输入，每个样例第一行输入两个整数n,m(2<=n<=200,1<=m<=1000)表示关卡和规则的数量，接下来m行规则，每行输入x,y,w（w<=1000）,表示从关卡x到y需要缴纳w的费用，保证题目有解，不会出现x=y的情况
输出描述:
输出一行，代表最少的钱
示例1
输入
复制
4 4
1 2 2
1 3 1
2 4 3
3 4 1