题目描述

给你一个有向无环图，求起点到终点的最长边。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$，分别表示点数和边数（$1 \le n \le 1000, 1\ le m \le 10^6$）。
接下来 $m$ 行，每行包含三个数 $u,v,w$，两两之间以一个空格分隔，表示从 $u$ 到 $v$ 有一条长度为 $w$ 的边。（1 \le u,v \le n, 1 \le w \le 10^5）
数据保证起点是 $1$，终点是 $n$，且只有 $1$ 号点入度为 $0$，只有 $n$ 号点出度为 $0$ 。

输出格式

输出从起点到终点的最长的那条路径的长度。

样例

3 3
1 2 2
2 3 2
1 3 5

5