#1935. 最长路

最长路

题目描述

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

输入格式

输入的第一行有两个整数,分别代表图的点数 nn 和边数 mm。

第 22 到第 (m+1)(m + 1) 行,每行 33 个整数 u,v,wu, v, w($u

输出格式

输出一行一个整数,代表 11 到 nn 的最长路。

若 11 无法到达 nn,请输出 −1-1。

样例

2 1
1 2 1
1

题目来源:洛谷 P1807