测试数据来自 system/2867

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　设 \(G\) 为有 \(n\) 个顶点的带权有向无环图，\(G\) 中各顶点的编号为 \(1\) 到 \(n\)，请设计算法，计算图 \(G\) 中 \(1\) 到 \(n\) 间的最长路径。

【输入格式】

　　输入的第一行有两个整数，分别代表图的点数 \(n\) 和边数 \(m\)。
　　第 \(2\) 到第 \(m + 1\) 行，每行 \(3\) 个整数 \(u, v, w\)，代表存在一条从 \(u\) 到 \(v\) 边权为 \(w\) 的边。

【输出格式】

　　输出一行一个整数，代表 \(1\) 到 \(n\) 的最长路。

【输入输出样例】

　Input

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

　Output

9

【数据范围】

　　对于 20% 的数据，\(n≤100，m≤1000\)。
　　对于 40% 的数据，\(n≤1000，m≤10000\)。
　　对于 100% 的数据，\(n≤1500，m≤50000，5≤w≤100000\)。

【来源】

　　Mr.he