#P1807. 最长路

最长路

题目描述

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

输入格式

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

22 到第 (m+1)(m + 1) 行,每行 33 个整数 u,v,wu, v, wu<vu<v),代表存在一条从 uuvv 边权为 ww 的边。

输出格式

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

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

2 1
1 2 1
1

提示

【数据规模与约定】

  • 对于 20%20\%的数据,n100n \leq 100m103m \leq 10^3
  • 对于 40%40\% 的数据,n103n \leq 10^3m104m \leq 10^{4}
  • 对于 100%100\% 的数据,1n15001 \leq n \leq 15000m5×1040 \leq m \leq 5 \times 10^41u,vn1 \leq u, v \leq n105w105-10^5 \leq w \leq 10^5