问题 26866. -- 最长路

26866: 最长路

时间限制: 1 Sec  内存限制: 128 MB
献花: 42  解决: 15
[献花][花圈]

题目描述

设G为有n个顶点的有向无环图,G中各顶点的编号为1到n,且当

输入

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

输出

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

样例输入

2 1
1 2 1

样例输出

1

提示

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


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


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



来源

[献花][花圈]