你好！我是你的OI金牌教练。

我们继续“历史+编程”的跨学科特训。 在之前的课程中，我们学习了拓扑排序（明朝永乐大典），解决了有向无环图（DAG）中的依赖顺序问题；也学习了最短路径（唐朝玄奘西行），解决了图中的最小代价问题。

今天，我们将这两者结合，穿越回三国时期，结合诸葛亮 “六出祁山” 中最为关键的粮草补给问题，来学习图论与动态规划的结合体—— DAG 上的最长路（关键路径） 问题。

这道题在知识点上体现了递进关系：

1. 从无权到有权：在拓扑排序中，我们只关心先后顺序；在这里，我们需要计算加权后的路径长度。
2. 从最短到最长：在普通图中求最长路是很难的（NP-Hard），但在**有向无环图（DAG）**中，我们可以利用 DP 在线性时间内解决。

第一部分：背景知识讲解

1. 诸葛亮北伐与粮草危机 (Northern Expeditions & Logistics)

三国后期，蜀汉丞相诸葛亮为了复兴汉室，六次出兵北伐曹魏。然而，蜀道艰险，运粮极其困难。“兵马未动，粮草先行”，粮草补给线的效率直接决定了战争的胜负。

2. 木牛流马 (Wooden Ox and Flowing Horse)

为了解决在崎岖山道上的运粮难题，诸葛亮发明了“木牛流马”。这是一种精妙的机械运输工具，能在栈道上高效运输粮食，极大缓解了蜀军的后勤压力。

3. 算法模型：关键路径 (Critical Path)

我们将蜀军的各个粮仓、转运站看作图中的节点，将运输道路看作有向边（粮草只能从后方运往前方，不可逆，因此无环），道路的长度或耗时看作边权。 为了制定作战计划，诸葛亮需要知道：整个运输网络中，耗时最长的一条运输线是多长？

• 这被称为 “关键路径”。因为这条路径最长，它决定了整个补给体系的最早完工时间。如果这条路径上的任何一个环节延误，整个大军的补给都会受影响。

第二部分：题目内容

题目名称：木牛流马的征途 (The Path of Wooden Ox)

题目描述

诸葛亮在汉中至五丈原之间建立了一个庞大的粮草运输网络。 该网络由 $N$ 个补给站组成，编号为 $1$ 到 $N$。 为了防止曹魏间谍逆向渗透，所有运输道路都是单向的。共有 $M$ 条单向运输线，第 $i$ 条线从补给站 $u_i$ 运往 $v_i$，耗时为 $w_i$。 经过严密的路线规划，整个运输网络不存在环路（即构成一个有向无环图 DAG）。

粮草可以从任意一个没有前置补给站的源头站点出发，经过若干条运输线，最终到达任意一个终点站点。 为了制定精确的进军时间表，诸葛亮需要你计算出：在这个运输网络中，耗时最长的一条运输路径的总耗时是多少？

输入格式

第一行包含两个正整数 $N, M$。

• $N$ 表示补给站的数量。
• $M$ 表示单向运输线的数量。

接下来 $M$ 行，每行包含三个正整数 $u, v, w$。

• 表示存在一条从 $u$ 到 $v$ 的单向运输线，耗时为 $w$。

输出格式

输出一行一个整数，表示整个运输网络中最长路径的总耗时。

输入输出样例 #1

输入：

5 6
1 2 2
1 3 5
2 4 10
2 5 3
3 5 4
4 5 2

输出：

14

样例 #1 解释： 图结构如下：

• $1 \to 2$ (2)
• $1 \to 3$ (5)
• $2 \to 4$ (10)
• $2 \to 5$ (3)
• $3 \to 5$ (4)
• $4 \to 5$ (2)

可能的路径有：

1. $1 \to 2 \to 5$：$2 + 3 = 5$
2. $1 \to 2 \to 4 \to 5$：$2 + 10 + 2 = 14$
3. $1 \to 3 \to 5$：$5 + 4 = 9$ 最长路径是 $1 \to 2 \to 4 \to 5$，耗时 14。

输入输出样例 #2

输入：

4 3
1 2 10
2 3 10
3 4 10

输出：

30

样例 #2 解释： 只有一条链：$1 \to 2 \to 3 \to 4$。 总长 $10+10+10 = 30$。

数据范围

对于 $100\%$ 的数据：

• $1 \le N \le 10^5$
• $1 \le M \le 2 \times 10^5$
• $1 \le w_i \le 1000$
• 保证图是 有向无环图 (DAG)。