J14 例题-3 滑雪

题目描述

在这个寒假里，鲍勃有一个在山庄滑雪的计划。

这个滑雪场有 $M$ 条不同的滑雪道，在这些转弯处有 $N$ 面不同的旗子。

从第 $S_i$ 面旗子到第 $T_i$ 面旗子的第 $i$ 条路径的长度为 $L_i$。

每条路径必须遵循高度减少的原则，起点必须严格高于终点。

一条可用的滑雪道将从一个旗子开始，沿着路径经过几个旗子，然后在另一个旗子结束。

现在，你应该帮助鲍勃找到滑雪场内最长的可用滑雪道。

输入格式

第一行包含一个整数 $T$，表示有T个样例。

在每个测试样例中，第一行包含两个整数 $N$ 和 $M$。

接下来的 $M$ 行中的每一行都包含三个整数 $S_i$、$T_i$ 和 $L_i$，描述了滑雪场中的一条路径。

输出格式

对于每个测试案例，输出一个整数，代表最长的滑雪道的长度。

样例输入

1
5 4
1 3 3
2 3 4
3 4 1
3 5 2

样例输出

6

样例分析

如上所述。

数据范围 对于 $100\%$ 的数据：$0<N \le 10000$，$0<M \le 100000$ ，$0<Li<1000$。