最长路_NOI导刊2010提高(07)

题目描述

设G为有n个顶点的有向无环图,G中各顶点的编号为1到n,且当为G中的一条边时有i < j。设w(i,j)为边的长度,请设计算法,计算图G中<1,n>间的最长路径。

输入输出格式

输入格式


输入文件longest.in的第一行有两个整数n和m,表示有n个顶点和m条边,接下来m行中每行输入3个整数a,b,v(表示从a点到b点有条边,边的长度为v)。

输出格式


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

输入输出样例

输入样例 #1

2 1
1 2 1

输出样例 #1

1

说明

20%的数据,n≤100,m≤1000 40%的数据,n≤1,000,m≤10000 100%的数据,n≤1,500,m≤50000,最长路径不大于10^9