题目描述
设G为有n个顶点的有向无环图,G中各顶点的编号为1到n,且如果G中的一条边是从i指向j,则有i < j。设w(i,j)为边的长度,请设计算法,计算图G中从顶点1到顶点n的最长路径。
输入描述
第一行有两个整数n和m(n <= 1500, m <= 50000),表示有n个顶点和m条边,接下来m行中每行输入3个整数a,b,v(表示从a点到b点有条边,边的长度为v,v <= 10^9)。
输出描述
一个整数,即1到n之间的最长路径.如果1到n之间没连通,输出-1。
样例输入
2 1
1 2 1
样例输出
1
提示