题目描述

设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。

输入样例#1：

2 1
1 2 1

输出样例#1：

1

数据范围

对于 20%的数据n≤100，m≤1000 
对于 40% 的数据n≤1000，m≤10000 
对于100% 的数据，1≤n≤1500，1≤m≤5×10000  1≤a,b≤n，−100000≤v≤100000