题目描述

设G为有n个顶点的有向无环图，G中各顶点的编号为1到n，且当为G中的一条边时有i < j。

设w（i，j）为边的长度，请设计算法，计算图G中<1，n>间的最长路径。

输入格式

第一行有两个整数n和m,表示有n个顶点和m条边，

接下来m行中每行输入3个整数a，b，v（表示从a点到b点有条边，边的长度为v）。

输出格式

一个整数，即1到n之间的最长路径.如果1到n之间没连通，输出-1。

样例数据

input

2 1

1 2 1

output

1

数据规模与约定

20%的数据，n≤100，m≤1000

40%的数据，n≤1,000，m≤10000

100%的数据，n≤1,500，m≤50000，最长路径不大于10^9

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$