最长路

题目描述

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

样例

提示

【数据规模与约定】 对于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。