题目描述
长江游乐俱乐部在长江上设置了n个游艇出租站，游客可以在这些游艇出租站用游艇，并在下游任何一个游艇出租站归还游艇，游艇出租站i到j之间的租金是Rij (1<=i<j<=n)，其中。试设计一个算法使得游客租用的费用最低。

输入格式
第 1 行两个整数 n 和 m ，表示有n个游艇出租站，接下来会有 m 个价格信息。
从第 2 行到第 m+1 行，是参考价格信息，每行有3个数字 i,j,Rij，表示从 i 站到 j 站的游艇出租费是Rij。
租费信息保证 i < j, 这意味着这些信息都是在上游租船，在下游还船。
租船信息都是单向的，如果存在从 i 站租船，j 站还船，费用为Rij，不能理解为可以在 j 站租船，i 站还船。

数据范围

• 5 <= n <= 1000
• 10 <= Rij <= 50000

输出格式
一个整数，代表从站点 1 到 站点 n 的最低费用。

样例

5 6
1 2 22
2 3 18
3 4 20
4 5 21
3 5 12
1 4 36

52

10 18
1 2 23
2 3 20
3 4 17
4 5 20
5 6 18
6 7 18
7 8 20
8 9 18
9 10 22
2 4 12
2 5 31
3 6 34
1 5 56
1 6 68
4 9 60
2 9 111
3 10 101
1 10 126

117

样例解释
样例1：最优方案可以是 1->2->3->5
样例2：最优方案可以是 1->2->4->9->10