混乱星球是一部n年以后拍摄的电影，这部电影和普通电影的区别在于，可以亲自体验剧情！
已知剧情有n个结束点，并且有m个不同的剧情分支。只有一个结束点结束之后，才可以继续往下体验。好消息是多个剧情可以同时体验。
现在要求出完成所有的剧情最少要花多少时间。

输入描述

第一行，两个整数n m，表示剧情结束点的个数和剧情的个数
接下来m行，每行3个整数，u v w，w是从剧情结束点u到剧情结束点v需要花费的时间

输出描述 Output Description

从结束点1到结束点n最少要花费的时间

样例输入


5 5
1 2 2
2 3 2
3 5 3
1 4 3
4 5 3



样例输出

7

数据范围及提示

n<=100，m<=120

从1到5，有两条剧情分支，1->2->3->5和1->4->5，耗时分别为7和6，但是要想体验5，必须体验完3和4，所以最后的时间取决于所以剧情路线中最大的一条。

有思路咩？

这个变形对我来说真的坏，我** 到n的前提还得到达其余所有，板子改成max20分，原封不动0分，模拟加持40分。。。有没有什么思路，蒟蒻的代码就不放了