### 问题描述 MIKU 酱是个玩游戏氪金的人，游戏公司给她制定了新的规则，如果想从关卡 $i$ 到关卡 $j$，你需要交一些钱就可以了，但同时，MIKU 酱的爸爸 zjw 很爱她，所以她可以每过一关就向她爸要一次钱，但她爸每次给他的钱是固定的，MIKU 酱是个不会节省的女孩，哪怕每次多出来的钱，她也会拿去买肥宅快乐水，所以每次要的钱一定花完，因为 MIKU 酱不想挨骂，所以希望每次他爸给她的钱最少。 tips：到达第 $n$ 关即通过，每到达一关一定能通过这关。 ### 输入格式 多组输入，每个样例第一行输入两个整数 $n,m(2\le n\le 200,1\le m\le 1000)$ 表示关卡和规则的数量，接下来 $m$ 行规则，每行输入 $x,y,w(w\le 1000)$，表示从关卡 $x$ 到 $y$ 需要缴纳 $w$ 的费用，保证题目有解，不会出现 $x=y$ 的情况。 ### 输出格式 输出一行，代表最少的钱 ### 样例输入 ```text 4 4 1 2 2 1 3 1 2 4 3 3 4 1 ``` ### 样例输出 ```text 1 ```