9213 - 最长路

设G为有n个顶点的带权有向无环图,G中各顶点的编号为1到n,请设计算法,计算图G中1, n间的最长路径。

输入

输入的第一行有两个整数,分别代表图的顶点数n和边数m。 第2到第 (m + 1)行,每行3个整数u, v, w(u<v),代表存在一条从u到v 边权为w的边。

输出

输出一行一个整数,代表1到n的最长路。 若1无法到达n,请输出-1。

样例

输入

2 1
1 2 1

输出

1

提示

【数据规模与约定】 对于20%的数据,n≤100,m≤10^3。 对于40% 的数据,n≤10^3 ,m≤10^4 。 对于 100% 的数据,1≤n≤1500,0≤m≤5×10^4,1≤u,v≤n,−10^5≤w≤10^5。

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题