题目描述

给定 $n$ 个点 $m$ 条边的有向图，可能不连通，可能有重边，也可能会有自环。求最长的路径(可以经过重复节点)，使得这条路径的编号和权值都严格单调递增，其中编号指输入的顺序。路径的长度是指经过边的数量。

输入格式

第一行两个整数 $n,m$。

第二行到第 $m+1$ 行，每行三个整数 $a,b,k$，表示顶点 $a$ 与顶点 $b$ 有一条边相连，边权为 $k$。

输出格式

一行一个整数，表示最长的路径的长度。

$1\leq n,m\leq10^5$，$0\le w_i\le10^5$。

retranslated by @皎月半洒花。

输入输出样例 #1

输入 #1

3 3
3 1 3
1 2 1
2 3 2

输出 #1

2

输入输出样例 #2

输入 #2

5 5
1 3 2
3 2 3
3 4 5
5 4 0
4 5 8

输出 #2

3